Joachim Schauer

Minimal Spanning Trees with Conflict Graphs

  • Andreas Darmann
  • Ulrich Pferschy
  • Joachim Schauer
    • Categories Graphs and Matroids, Network Optimization Tags ,

    For the classical minimum spanning tree problem we introduce disjunctive constraints for pairs of edges which can not be both included in the spanning tree at the same time. These constraints are represented by a conflict graph whose vertices correspond to the edges of the original graph. Edges in the conflict graph connect conflicting edges … Read more

    The Knapsack Problem with Conflict Graphs

  • Ulrich Pferschy
  • Joachim Schauer
    • Categories 0-1 Programming, Graphs and Matroids Tags ,

    We extend the classical 0-1 knapsack problem by introducing disjunctive constraints for pairs of items which are not allowed to be packed together into the knapsack. These constraints are represented by edges of a conflict graph whose vertices correspond to the items of the knapsack problem. Similar conditions were treated in the literature for bin … Read more