A push-relabel approximation algorithm for approximating the minimum-degree MST problem and its generalization to matroids

DOI10.1016/J.TCS.2009.07.029MaRDI QIDQ1035684zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

spanning treesapproximation algorithmsdegree-bounded network designpush-relabel

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25) Network design and communication in computer systems (68M10)

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

Cites work

• scientific article; zbMATH DE number 5485590 (Why is no real title available?)
• scientific article; zbMATH DE number 5485591 (Why is no real title available?)
• A Matter of Degree: Improved Approximation Algorithms for Degree-Bounded Minimum Spanning Trees
• A Push-Relabel Algorithm for Approximating Degree Bounded MSTs
• 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
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Degree Bounded Matroids and Submodular Flows
• Degree-bounded minimum spanning trees
• Delegate and Conquer: An LP-Based Approximation Algorithm for Minimum Degree MSTs
• Euclidean bounded-degree spanning tree ratios
• Low-Degree Spanning Trees of Small Weight
• Maximum matching and a polyhedron with 0,1-vertices
• On two geometric problems related to the travelling salesman problem
• Primal-dual meets local search: approximating MST's with nonuniform degree bounds
• Survivable network design with degree or order constraints

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
• Network design with weighted degree constraints
• Bounded-degree light approximate shortest-path trees in doubling metrics
• 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.
• Chain-constrained spanning trees
• Degree bounded matroids and submodular flows

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)