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

DOI10.1007/11786986_16zbMath1223.90074OpenAlexW2112594285MaRDI QIDQ3613758

Mohit Singh, R. Ravi

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)

Related Items (10)

Spanning trees with minimum weighted degrees ⋮ What would Edmonds do? Augmenting paths and witnesses for degree-bounded MSTs ⋮ On generalizations of network design problems with degree bounds ⋮ Network design with weighted degree constraints ⋮ Bounded-degree light approximate shortest-path trees in doubling metrics ⋮ An approximation algorithm for a symmetric generalized multiple depot, multiple travelling salesman problem ⋮ Budgeted matching and budgeted matroid intersection via the gasoline puzzle ⋮ Network Design with Weighted Degree Constraints ⋮ 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

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