A push-relabel approximation algorithm for approximating the minimum-degree MST problem and its generalization to matroids
DOI10.1016/J.TCS.2009.07.029zbMATH Open1205.68509OpenAlexW2083383617MaRDI QIDQ1035684FDOQ1035684
Authors: J. Blot 
Publication date: 4 November 2009
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2009.07.029
Recommendations
- A Push-Relabel Algorithm for Approximating Degree Bounded MSTs
- What would Edmonds do? Augmenting paths and witnesses for degree-bounded MSTs
- Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
- A Matter of Degree: Improved Approximation Algorithms for Degree-Bounded Minimum Spanning Trees
- A matter of degree: improved approximation algorithms for degree-bounded minimum spanning trees
Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25) Network design and communication in computer systems (68M10)
Cites Work
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- Maximum matching and a polyhedron with 0,1-vertices
- Degree Bounded Matroids and Submodular Flows
- A Matter of Degree: Improved Approximation Algorithms for Degree-Bounded Minimum Spanning Trees
- 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
- Title not available (Why is that?)
- Delegate and Conquer: An LP-Based Approximation Algorithm for Minimum Degree MSTs
- A Push-Relabel Algorithm for Approximating Degree Bounded MSTs
- Degree-bounded minimum spanning trees
- On two geometric problems related to the travelling salesman problem
- Survivable network design with degree or order constraints
- Title not available (Why is that?)
- Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
- Low-Degree Spanning Trees of Small Weight
- Euclidean bounded-degree spanning tree ratios
- Primal-dual meets local search: approximating MST's with nonuniform degree bounds
Cited In (12)
- 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
- Bounded-degree light approximate shortest-path trees in doubling metrics
- Network design with weighted degree constraints
- What would Edmonds do? Augmenting paths and witnesses for degree-bounded MSTs
- A Push-Relabel Algorithm for Approximating Degree Bounded MSTs
- A 3/2-Approximation for the Metric Many-Visits Path TSP
- Matroidal degree-bounded minimum spanning trees
- The Maximum Binary Tree Problem.
- Degree bounded matroids and submodular flows
- Chain-constrained spanning trees
This page was built for publication: A push-relabel approximation algorithm for approximating the minimum-degree MST problem and its generalization to matroids
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1035684)
