Delegate and Conquer: An LP-Based Approximation Algorithm for Minimum Degree MSTs

DOI10.1007/11786986_16MaRDI QIDQ3613758zbMATH OpenOpenAlexFDO

Authors R. Ravi, Mohit Singh

Publication date 12 March 2009

Published in Automata, Languages and Programming (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/11786986_16

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Recommendations

• 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
• Primal-dual meets local search: approximating MST's with nonuniform degree bounds
• Primal-Dual Meets Local Search: Approximating MSTs With Nonuniform Degree Bounds
• scientific article; zbMATH DE number 742978

Cited in

(12)

• A push-relabel approximation algorithm for approximating the minimum-degree MST problem and its generalization to matroids
• Budgeted matching and budgeted matroid intersection via the gasoline puzzle
• Approximating minimum bounded degree spanning trees to within one of optimal
• Network design with weighted degree constraints
• 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
• Fast combinatorial algorithms for efficient sortation
• Fast combinatorial algorithms for efficient sortation
• md-MST is NP-hard for \(d\geq 3\)
• Spanning trees with minimum weighted degrees
• An approximation algorithm for a symmetric generalized multiple depot, multiple travelling salesman problem

This page was built for publication: Delegate and Conquer: An LP-Based Approximation Algorithm for Minimum Degree MSTs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3613758)