What would Edmonds do? Augmenting paths and witnesses for degree-bounded MSTs
From MaRDI portal
Publication:2391179
DOI10.1007/S00453-007-9115-5zbMATH Open1180.90347OpenAlexW2176322034MaRDI QIDQ2391179FDOQ2391179
Authors: Yanyan Li 
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
Recommendations
- Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
- A Push-Relabel Algorithm for Approximating Degree Bounded MSTs
- Primal-dual meets local search: approximating MST's with nonuniform degree bounds
- Primal-Dual Meets Local Search: Approximating MSTs With Nonuniform Degree Bounds
- A push-relabel approximation algorithm for approximating the minimum-degree MST problem and its generalization to matroids
Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Combinatorial optimization (90C27) Approximation algorithms (68W25)
Cites Work
- Paths, Trees, and Flowers
- Topological design of centralized computer networks—formulations and algorithms
- Maximum matching and a polyhedron with 0,1-vertices
- An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
- Network Flow and Testing Graph Connectivity
- Analysis of Christofides' heuristic: some paths are more difficult than cycles
- Approximating minimum bounded degree spanning trees to within one of optimal
- Approximating the Minimum-Degree Steiner Tree to within One of Optimal
- Delegate and Conquer: An LP-Based Approximation Algorithm for Minimum Degree MSTs
- A Push-Relabel Algorithm for Approximating Degree Bounded MSTs
- Many birds with one stone
- Degree-bounded minimum spanning trees
- On two geometric problems related to the travelling salesman problem
- Toughness, trees, and walks
- Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
- Approximation algorithms for degree-constrained minimum-cost network-design problems
- Low-Degree Spanning Trees of Small Weight
- A matter of degree: improved approximation algorithms for degree-bounded minimum spanning trees
- Title not available (Why is that?)
- Euclidean bounded-degree spanning tree ratios
- Primal-dual meets local search: approximating MST's with nonuniform degree bounds
Cited In (16)
- A push-relabel approximation algorithm for approximating the minimum-degree MST problem and its generalization to matroids
- Approximating minimum bounded degree spanning trees to within one of optimal
- The maximum binary tree problem
- Refuting a conjecture of goemans on bounded degree spanning trees
- On generalizations of network design problems with degree bounds
- Bounded-degree light approximate shortest-path trees in doubling metrics
- Network design with weighted degree constraints
- Title not available (Why is that?)
- Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
- A Push-Relabel Algorithm for Approximating Degree Bounded MSTs
- A 3/2-Approximation for the Metric Many-Visits Path TSP
- Primal-dual meets local search: approximating MST's with nonuniform degree bounds
- The Maximum Binary Tree Problem.
- Chain-constrained spanning trees
- Primal-Dual Meets Local Search: Approximating MSTs With Nonuniform Degree Bounds
- Approximating min-cost chain-constrained spanning-trees: a reduction from weighted to unweighted problems
This page was built for publication: What would Edmonds do? Augmenting paths and witnesses for degree-bounded MSTs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2391179)
