Spanning trees with minimum weighted degrees

DOI10.1016/j.ipl.2007.06.011zbMath1183.05079OpenAlexW2117220605MaRDI QIDQ2380008

Shayan Oveis Gharan, Morteza Zadimoghaddam, Amin S. Sayedi R., Kian Mirjalali, Hamid Mahini, Mohammad Ghodsi

Publication date: 24 March 2010

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2007.06.011

zbMATH Keywords

graph algorithmsapproximation algorithmsmetric graphspanning trees

Mathematics Subject Classification ID

Trees (05C05) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

Network design with weighted degree constraints ⋮ Network Design with Weighted Degree Constraints

Cites Work

• Unnamed Item
• Complexity of spanning tree problems: Part I
• On the complexity of finding multi-constrained spanning trees
• Efficient algorithms for maximum lifetime data gathering and aggregation in wireless sensor networks.
• A matter of degree
• Delegate and Conquer: An LP-Based Approximation Algorithm for Minimum Degree MSTs
• A Push-Relabel Algorithm for Approximating Degree Bounded MSTs
• The complexity of restricted spanning tree problems
• Approximation algorithms for finding low-degree subgraphs
• The Bounded Path Tree Problem
• Many birds with one stone
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques