Degree-bounded minimum spanning trees Original Research Article

Given image points in the Euclidean plane, the degree-image minimum spanning tree (MST) problem asks for a spanning tree of minimum weight in which the degree of each vertex is at most image. The problem is NP-hard for image, while the NP-hardness of the problem is open for image. The problem is polynomial-time solvable when image. 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 image times the weight of an MST.