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
On generalizations of network design problems with degree bounds, Network design with weighted degree constraints
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
