Determining a Minimum Spanning Tree with Disjunctive Constraints

DOI10.1007/978-3-642-04428-1_36MaRDI QIDQ3645334zbMATH OpenOpenAlexWikidataFDO

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

zbMATH Keywords

minimum spanning treeconflict graph

Mathematics Subject Classification ID

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)

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

Cited in

(24)

• Parameterized complexity of conflict-free matchings and paths
• Minimum spanning tree with conflicting edge pairs: a branch-and-cut approach
• Conflict free version of covering problems on graphs: classical and parameterized
• 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
• The minimum spanning tree problem with conflict constraints and its variations
• Maximum weight perfect matching problem with additional disjunctive conflict constraints
• Paths, trees and matchings under disjunctive constraints
• On conflict-free spanning tree: algorithms and complexity
• The quadratic minimum spanning tree problem and its variations
• The knapsack problem with forfeit sets
• Polyhedral results and stronger Lagrangean bounds for stable spanning trees
• 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)