A polynomial-time approximation scheme for Steiner tree in planar graphs
July 4, 2009
Glencora Borradaile, Philip Klein and Claire Mathieu
We give a Polynomial-Time Approximation Scheme (PTAS) for the Steiner tree problem in planar graphs. The running time is O(n log n).
ACM Transactions on Algorithms (special issue for SODA 2007), 5(3), 2009.
