Faster geometric $k$-point MST approximation

David Eppstein
Computational Geometry Theory & Applications 8:231–240, Oct 1997
Tech. report 95-13, Univ. of California, Irvine, Dept. of Information and Computer Science, 1995
Mathematical Reviews 98d:68199
http://www.ics.uci.edu/~eppstein/pubs/Epp-TR-95-13.pdf

Cited by:

• Guillotine subdivisions approximate polygonal subdivisions: a simple new method for the geometric $k$-MST problem
• A 3-approximation for the minimum tree spanning $k$ vertices
• An $O(\log k)$-approximation algorithm for the $k$ minimum spanning tree problem in the plane
• Polynomial time approximation schemes for Euclidean TSP and other geometric problems
• A constant-factor approximation algorithm for the geometric $k$-MST problem in the plane
• Asymptotic theory of greedy approximations to minimal $K$-point random graphs
• Geometric shortest paths and network optimization
• Local search algorithms for the $k$-cardinality tree problem