Determining a Minimum Spanning Tree with Disjunctive Constraints
From MaRDI portal
Publication:3645334
DOI10.1007/978-3-642-04428-1_36zbMath1260.68171OpenAlexW179052057WikidataQ61638340 ScholiaQ61638340MaRDI QIDQ3645334
Joachim Schauer, Ulrich Pferschy, Andreas Darmann
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
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)
Related Items
Minimum spanning tree with conflicting edge pairs: a branch-and-cut approach ⋮ The quadratic minimum spanning tree problem and its variations ⋮ Parameterized complexity of conflict-free matchings and paths ⋮ Minimum cost noncrossing flow problem on layered networks ⋮ Minimum cost flow problem with conflicts ⋮ 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 ⋮ Precedence-constrained arborescences ⋮ Polyhedral results and stronger Lagrangean bounds for stable spanning trees ⋮ Maximum weight perfect matching problem with additional disjunctive conflict constraints ⋮ The minimum spanning tree problem with conflict constraints and its variations ⋮ Paths, trees and matchings under disjunctive constraints ⋮ Fixed cardinality stable sets ⋮ Exploring the Kernelization Borders for Hitting Cycles ⋮ Maximum weighted matching with few edge crossings for 2-layered bipartite graph ⋮ A branch and cut algorithm for minimum spanning trees under conflict constraints ⋮ 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 ⋮ A unifying model for locally constrained spanning tree problems
