Paper Info
Title
A Polynomial-Time Approximation Scheme for Euclidean Steiner Forest
Abstract
We give a randomized O(n polylog n)-time approximation scheme for the Steiner forest problem in the Euclidean plane. For every fixed ε > 0 and given n terminals in the plane with connection requests between some pairs of terminals, our scheme finds a (1 + ε) approximation to the minimum-length forest that connects every requested pair of terminals.
Year
DOI
Venue
2008
10.1145/2629654
ACM Transactions on Algorithms
Keywords
DocType
Volume
computational complexity,polynomial approximation,Euclidean Steiner forest,minimum-length forest,polynomial-time approximation scheme,Euclidean plane,Steiner forest,approximation algorithm,approximation scheme
Conference
11
Issue
ISSN
Citations 
3
1549-6325
11
PageRank 
References 
Authors
0.59
18
3
Name
Order
Citations
PageRank
Glencora Borradaile127521.24
Philip N. Klein22681256.19
Claire Mathieu345225.78