On the bounded-hop MST problem on random Euclidean instances
The d-Dim h-HOPS MST problem is defined as follows: given a set S of points in the d-dimensional Euclidean space and S E S, find a minimum-cost spanning tree for S rooted at s with height at most h. We investigate the problem for any constant h and d > 0. We prove the first nontrivial lower bound on the solution cost for almost all Euclidean instances (i.e. the lower bound holds with high probability). Then we introduce an easy-to-implement, fast divide et impera heuristic and we prove that its solution cost matches the lower bound. (C) 2007 Elsevier B.V. All rights reserved.
approximation algorithms randomized algorithms bounded height minimum spanning tree