Degree-bounded Minimum Spanning Trees
March 6, 2009 - Jothi, Raja; Raghavachari, Balaji
Print
EmailJournal or Book Title: DISCRETE APPLIED MATHEMATICS
Volume/Issue: 157
Year Published: 2009
Given n points in the Euclidean plane, the degree-A minimum spanning tree (MST) problem asks for a spanning tree of minimum weight in which the degree of each vertex is at most delta. The problem is NP-hard for 2 <= delta <= 3, while the NP-hardness of the problem is open for delta = 4. The problem is polynomial-time solvable when delta = 5. By presenting an improved approximation analysis for Chan's degree-4 MST algorithm [T. Chan, Euclidean bounded-degree spanning tree ratios, Discrete & Computational Geometry 32 (2004) 177-194], we show that, for any arbitrary collection of points in the Euclidean plane, there always exists a degree-4 spanning tree of weight at most (root 2 + 2)/3 < 1.1381 times the weight of an MST. Published by Elsevier B.V.
DOI: 10.1016/j.dam.2008.03.037
Type of Publication: Article
