Spanning trees with minimum weighted degrees

DOI10.1016/J.IPL.2007.06.011MaRDI QIDQ2380008zbMATH OpenOpenAlexFDO

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

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

spanning treesapproximation algorithmsgraph algorithmsmetric graph

Mathematics Subject Classification ID

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

Recommendations

• Approximating Minimum Max-Stretch Spanning Trees on Unweighted Graphs
• Low-Degree Spanning Trees of Small Weight
• scientific article; zbMATH DE number 742978
• Approximating the degree-bounded minimum diameter spanning tree problem

Cites work

• scientific article; zbMATH DE number 742978 (Why is no real title available?)
• A Push-Relabel Algorithm for Approximating Degree Bounded MSTs
• A matter of degree: improved approximation algorithms for degree-bounded minimum spanning trees
• Approximation algorithms for finding low-degree subgraphs
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• Complexity of spanning tree problems: Part I
• Delegate and Conquer: An LP-Based Approximation Algorithm for Minimum Degree MSTs
• Efficient algorithms for maximum lifetime data gathering and aggregation in wireless sensor networks.
• Many birds with one stone
• On the complexity of finding multi-constrained spanning trees
• The Bounded Path Tree Problem
• The complexity of restricted spanning tree problems

Cited in

(12)

• The vertex degrees of minimum spanning trees
• Network design with weighted degree constraints
• Spanning trees in graphs of minimum degree 4 or 5
• Network Design with Weighted Degree Constraints
• Minimum Spanning Tree with Neighborhoods
• The degree-preserving spanning tree problem in strongly chordal and directed path graphs
• Minimum spanning trees in networks with varying edge weights
• Minimum edge ranking spanning trees of split graphs
• Polynomial time approximation schemes for the constrained minimum spanning tree problem
• Low degree spanning trees of small weight
• Online Minimum Spanning Tree with Advice
• scientific article; zbMATH DE number 2011838 (Why is no real title available?)

This page was built for publication: Spanning trees with minimum weighted degrees

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