Degree-bounded minimum spanning trees

作     者：Jothi, Raja Raghavachari, Balaji 

作者机构：NHLBI Lab Mol Immunol NIH Bethesda MD 20892 USA Univ Texas Dallas Dept Comp Sci Richardson TX 75080 USA 

出 版 物：《DISCRETE APPLIED MATHEMATICS》 (离散应用数学)

年 卷 期：2009年第157卷第5期

页      面：960-970页

核心收录：

学科分类：07[理学] 0701[理学-数学] 070101[理学-基础数学] 

基　　金：National Science Foundation [CCR-9820902] 

主　　题：Spanning trees Minimum spanning trees Approximation algorithm Geometric optimization Network design 

摘      要：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.