A unifying model for locally constrained spanning tree problems
From MaRDI portal
Publication:2045044
DOI10.1007/s10878-021-00740-2zbMath1470.05035arXiv2005.10328OpenAlexW3152779679MaRDI QIDQ2045044
Publication date: 11 August 2021
Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2005.10328
Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Trees (05C05) Combinatorial optimization (90C27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Directed graphs (digraphs), tournaments (05C20)
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Branch-and-cut-and-price algorithms for the degree constrained minimum spanning tree problem
- The maximum flow problem with disjunctive constraints
- The minimum spanning tree problem with conflict constraints and its variations
- Online variable-sized bin packing with conflicts
- On the maximum acyclic subgraph problem under disjunctive constraints
- The min-degree constrained minimum spanning tree problem: formulations and branch-and-cut algorithm
- Bounded-angle spanning tree: modeling networks with angular constraints
- Paths, trees and matchings under disjunctive constraints
- On the minimum diameter spanning tree problem
- Min-degree constrained minimum spanning tree problem: new formulation via Miller-Tucker-Zemlin constraints
- Minimum spanning tree with conflicting edge pairs: a branch-and-cut approach
- Complexity of spanning tree problems: Part I
- On the complexity of finding multi-constrained spanning trees
- Which problems have strongly exponential complexity?
- Min-degree constrained minimum spanning tree problem with fixed centrals and terminals: complexity, properties and formulations
- Approximating the degree-bounded minimum diameter spanning tree problem
- Low-degree minimum spanning trees
- A branch and cut algorithm for minimum spanning trees under conflict constraints
- Solutions for the knapsack problem with conflict and forcing graphs of bounded clique-width
- Modeling and solving the angular constrained minimum spanning tree problem
- The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
- md-MST is NP-hard for
- Min-degree constrained minimum spanning tree problem: complexity, properties, and formulations
- Matroid Intersection
- On two geometric problems related to the travelling salesman problem
- Easy problems for tree-decomposable graphs
- Determining a Minimum Spanning Tree with Disjunctive Constraints
- Minimum Diameter Spanning Trees and Related Problems
- Trees in Graphs with Conflict Edges or Forbidden Transitions
- Computational Complexity
- Approximating Minimum Bounded Degree Spanning Trees to within One of Optimal
- Parameterized Algorithms
- The complexity of theorem-proving procedures
- On the complexity of \(k\)-SAT
- Comparison of algorithms for the degree constrained minimum spanning tree
- Two dependency constrained spanning tree problems
