A constant-factor approximation for the k-MST problem in the plane
Conference Paper, Proceedings of 27th Annual ACM Symposium on Theory of Computing (STOC '95), pp. 294 - 302, May, 1995
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].
BibTeX
@conference{Blum-1995-16190,author = {Avrim Blum and Prasad Chalasani and Santosh Vempala},
title = {A constant-factor approximation for the k-MST problem in the plane},
booktitle = {Proceedings of 27th Annual ACM Symposium on Theory of Computing (STOC '95)},
year = {1995},
month = {May},
pages = {294 - 302},
}
Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.