A constant-factor approximation for the <i>k</i>-MST problem in the plane

Abstract

We present an algorithm that gives a constant factor approximation for the following problem. Given a set of n points in the plane with a Euclidean distance metric and an integer k < n, find the tree of least weight that spans k points. If desired, one may also specify in the problem a "root vertex" that must be in the tree. Our result improves on the previous best bound of O(log k) of Garg and Hochbaum [5], which in turn improved a previous 0(kl/4) bound of Ravi et al [9].