An O ( n log n ) approximation scheme for Steiner tree in planar graphs
Authors:
Open Access
- 4 July 2009
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Algorithms
- Vol. 5 (3) , 1-31
Abstract
We give a Polynomial-Time Approximation Scheme (PTAS) for the Steiner tree problem in planar graphs. The running time is O ( n log n ).Keywords
Funding Information
- Division of Computing and Communication Foundations (CCF-0635089)
This publication has 25 references indexed in Scilit:
- Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problemsJournal of the ACM, 1998
- Faster Shortest-Path Algorithms for Planar GraphsJournal of Computer and System Sciences, 1997
- Improved Approximations for the Steiner Tree ProblemJournal of Algorithms, 1994
- Approximation algorithms for NP-complete problems on planar graphsJournal of the ACM, 1994
- An 11/6-approximation algorithm for the network steiner problemAlgorithmica, 1993
- Faster exact algorithms for steiner trees in planar networksNetworks, 1990
- The Steiner problem with edge lengths 1 and 2Information Processing Letters, 1989
- A faster approximation algorithm for the Steiner problem in graphsInformation Processing Letters, 1988
- Convexity and the Steiner tree problemNetworks, 1988
- Efficient Planarity TestingJournal of the ACM, 1974