| 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 finite 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 | |||||||||||||||||
Publication details | |||||||||||||||||
| |||||||||||||||||