Determining a Minimum Spanning Tree with Disjunctive Constraints
DOI10.1007/978-3-642-04428-1_36zbMATH Open1260.68171OpenAlexW179052057WikidataQ61638340 ScholiaQ61638340MaRDI QIDQ3645334FDOQ3645334
Authors: Andreas Darmann, Ulrich Pferschy, Joachim Schauer 
Publication date: 17 November 2009
Published in: Algorithmic Decision Theory (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-642-04428-1_36
Recommendations
- The Minimum Spanning Tree Constraint
- A constrained minimum spanning tree problem
- The minimum weight spanning tree with constraints
- Exact algorithms for finding constrained minimum spanning trees
- On the minimum diameter spanning tree problem
- Minimum Diameter Spanning Trees and Related Problems
- The constrained minimum spanning tree problem
- Solving diameter-constrained minimum spanning tree problems by constraint programming
- A Note on Finding Minimum-Cost Edge-Disjoint Spanning Trees
- Minimal spanning trees with a constraint on the number of leaves
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Cited In (24)
- Parameterized complexity of conflict-free matchings and paths
- Conflict free version of covering problems on graphs: classical and parameterized
- Minimum spanning tree with conflicting edge pairs: a branch-and-cut approach
- Exact solution algorithms for the maximum flow problem with additional conflict constraints
- A Lagrangian approach for the minimum spanning tree problem with conflicting edge pairs
- Trees in graphs with conflict edges or forbidden transitions
- Fixed cardinality stable sets
- The Minimum Spanning Tree Constraint
- Minimum cost flow problem with conflicts
- Precedence-constrained arborescences
- Exploring the kernelization borders for hitting cycles
- A unifying model for locally constrained spanning tree problems
- Assignment problem with conflicts
- Parameterized complexity of conflict-free matchings and paths
- Maximum weight perfect matching problem with additional disjunctive conflict constraints
- The minimum spanning tree problem with conflict constraints and its variations
- On conflict-free spanning tree: algorithms and complexity
- Paths, trees and matchings under disjunctive constraints
- The knapsack problem with forfeit sets
- Polyhedral results and stronger Lagrangean bounds for stable spanning trees
- The quadratic minimum spanning tree problem and its variations
- A branch and cut algorithm for minimum spanning trees under conflict constraints
- Maximum weighted matching with few edge crossings for 2-layered bipartite graph
- Minimum cost noncrossing flow problem on layered networks
This page was built for publication: Determining a Minimum Spanning Tree with Disjunctive Constraints
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3645334)
