Paths, trees and matchings under disjunctive constraints

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

zbMATH Keywords

shortest path; matching; binary constraints; minimal spanning tree; conflict graph

Mathematics Subject Classification ID

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, Unnamed Item, Fair Packing of Independent Sets, Exploring the Kernelization Borders for Hitting Cycles, Conflict free version of covering problems on graphs: classical and parameterized, Parameterized complexity of conflict-free set cover, Fair allocation algorithms for indivisible items under structured conflict constraints, Minimum cost flow problem with conflicts, Two dependency constrained spanning tree problems, A Lagrangian approach for the minimum spanning tree problem with conflicting edge pairs, On conflict-free spanning tree: algorithms and complexity, The knapsack problem with forfeit sets, Polyhedral results and stronger Lagrangean bounds for stable spanning trees, Maximum weight perfect matching problem with additional disjunctive conflict constraints, 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, Minimum spanning tree with conflicting edge pairs: a branch-and-cut approach, The transportation problem with conflicts, 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, Fixed cardinality stable sets, Maximum weighted matching with few edge crossings for 2-layered bipartite graph, Approximation of knapsack problems with conflict and forcing graphs, Exact solution algorithms for the maximum flow problem with additional conflict constraints, A unifying model for locally constrained spanning tree problems, The unsuitable neighbourhood inequalities for the fixed cardinality stable set polytope, Matching-based capture strategies for 3D heterogeneous multiplayer reach-avoid differential games, The generalized dependency constrained spanning tree problem, A matheuristic for a customer assignment problem in direct marketing, Parameterized complexity of conflict-free matchings and paths, 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, The rainbow Steiner tree problem, Fair allocation of indivisible items with conflict graphs

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