May
1995
A constant-factor approximation for the k-MST problem in the plane
Authors:
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].
copied = false, 2000);
">
@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},
}
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},
}