What would Edmonds do? Augmenting paths and witnesses for degree-bounded MSTs
From MaRDI portal
Publication:2391179
DOI10.1007/s00453-007-9115-5zbMath1180.90347MaRDI QIDQ2391179
Publication date: 24 July 2009
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00453-007-9115-5
90C35: Programming involving graphs or networks
68Q25: Analysis of algorithms and problem complexity
90C27: Combinatorial optimization
68W25: Approximation algorithms
Related Items
Approximating Minimum Bounded Degree Spanning Trees to within One of Optimal, On generalizations of network design problems with degree bounds, Network design with weighted degree constraints, Chain-constrained spanning trees, Approximating MIN-cost chain-constrained spanning trees: a reduction from weighted to unweighted problems
Cites Work
- Unnamed Item
- Unnamed Item
- Degree-bounded minimum spanning trees
- Analysis of Christofides' heuristic: some paths are more difficult than cycles
- A matter of degree
- On two geometric problems related to the travelling salesman problem
- Approximating minimum bounded degree spanning trees to within one of optimal
- Primal-dual meets local search
- Delegate and Conquer: An LP-Based Approximation Algorithm for Minimum Degree MSTs
- A Push-Relabel Algorithm for Approximating Degree Bounded MSTs
- Topological design of centralized computer networks—formulations and algorithms
- Network Flow and Testing Graph Connectivity
- Approximating the Minimum-Degree Steiner Tree to within One of Optimal
- Low-Degree Spanning Trees of Small Weight
- Many birds with one stone
- Paths, Trees, and Flowers
- Euclidean bounded-degree spanning tree ratios
- Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
- Maximum matching and a polyhedron with 0,1-vertices
- An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
- Approximation algorithms for degree-constrained minimum-cost network-design problems