Paths, trees and matchings under disjunctive constraints
From MaRDI portal
Publication:643009
DOI10.1016/j.dam.2010.12.016zbMath1228.05186WikidataQ61638315 ScholiaQ61638315MaRDI QIDQ643009
Andreas Darmann, Ulrich Pferschy, Gerhard J. Woeginger, Joachim Schauer
Publication date: 27 October 2011
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.dam.2010.12.016
05C05: Trees
05C35: Extremal problems in graph theory
05C38: Paths and cycles
05C70: Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
Related Items
Trees in Graphs with Conflict Edges or Forbidden Transitions, The maximum flow problem with disjunctive constraints, On the maximum acyclic subgraph problem under disjunctive constraints, Completion of partial Latin hypercube designs: NP-completeness and inapproximability, The quadratic minimum spanning tree problem and its variations, A characterization of linearizable instances of the quadratic minimum spanning tree problem, A branch-and-bound algorithm for the minimum cost bipartite perfect matching problem with conflict pair constraints, Budgeted colored matching problems, Approximation of knapsack problems with conflict and forcing graphs, A branch and cut algorithm for minimum spanning trees under conflict constraints, Assignment problem with conflicts, The quadratic balanced optimization problem, Optimal base complexes for quadrilateral meshes, Minimum cost noncrossing flow problem on layered networks
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The maximum flow problem with disjunctive constraints
- Approximation algorithms for time constrained scheduling
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- An approximation scheme for bin packing with conflicts
- The Knapsack Problem with Conflict Graphs
- Matroid Intersection
- Determining a Minimum Spanning Tree with Disjunctive Constraints
