| Let (2007) | |||||||||||||||||
Abstract | |||||||||||||||||
| Let K be the worst-case (supremum) ratio of the weight of the minimum degree-K spanning tree to the weight of the minimum spanning tree, over all nite point sets in the Euclidean plane. It is known that 2 = 2 and 5 = 1. In STOC'94, Khuller, Raghavachari, and Young established the following inequalities: 1:103 3 1:5 and 1:035 4 1:25. We present the rst improved upper bounds: 3 1:402 and 4 1:143. As a result, we obtain better approximation algorithms for Euclidean minimum bounded-degree spanning trees. | |||||||||||||||||
Publication details | |||||||||||||||||
| |||||||||||||||||