Paths, trees and matchings under disjunctive constraints
From MaRDI portal
Publication:643009
DOI10.1016/j.dam.2010.12.016zbMath1228.05186OpenAlexW2116638623WikidataQ61638315 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
Trees (05C05) Extremal problems in graph theory (05C35) Paths and cycles (05C38) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)
Related Items (40)
Optimal base complexes for quadrilateral meshes ⋮ Matching-based capture strategies for 3D heterogeneous multiplayer reach-avoid differential games ⋮ Fair Packing of Independent Sets ⋮ Minimum spanning tree with conflicting edge pairs: a branch-and-cut approach ⋮ The transportation problem with conflicts ⋮ The generalized dependency constrained spanning tree problem ⋮ The quadratic minimum spanning tree problem and its variations ⋮ The maximum flow problem with disjunctive constraints ⋮ A matheuristic for a customer assignment problem in direct marketing ⋮ The rainbow Steiner tree problem ⋮ Parameterized complexity of conflict-free matchings and paths ⋮ Minimum cost noncrossing flow problem on layered networks ⋮ 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 ⋮ A characterization of linearizable instances of the quadratic minimum spanning tree problem ⋮ Fair allocation of indivisible items with conflict graphs ⋮ On the maximum acyclic subgraph problem under disjunctive constraints ⋮ Fixed cardinality stable sets ⋮ A branch-and-bound algorithm for the minimum cost bipartite perfect matching problem with conflict pair constraints ⋮ Budgeted colored matching problems ⋮ Exploring the Kernelization Borders for Hitting Cycles ⋮ Completion of partial Latin hypercube designs: NP-completeness and inapproximability ⋮ Maximum weighted matching with few edge crossings for 2-layered bipartite graph ⋮ Trees in Graphs with Conflict Edges or Forbidden Transitions ⋮ A branch and cut algorithm for minimum spanning trees under conflict constraints ⋮ Approximation of knapsack problems with conflict and forcing graphs ⋮ Assignment problem with conflicts ⋮ Exact solution algorithms for the maximum flow problem with additional conflict constraints ⋮ Unnamed Item ⋮ Conflict free version of covering problems on graphs: classical and parameterized ⋮ Parameterized complexity of conflict-free set cover ⋮ A unifying model for locally constrained spanning tree problems ⋮ The unsuitable neighbourhood inequalities for the fixed cardinality stable set polytope ⋮ The quadratic balanced optimization problem
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
This page was built for publication: Paths, trees and matchings under disjunctive constraints
