Steiner tree in planar graphs: An O(n log n) approximation scheme with singly-exponential dependence on epsilon
August 4, 2007
Glencora Borradaile, Philip Klein and Claire Mathieu
We give an algorithm that, for any ε > 0, any undirected planar graph G, and any set S of nodes of G, computes a (1+ε)-optimal Steiner tree in G that spans the nodes of S. The algorithm takes time O(2poly(1/ε)n log n).
Proceedings of the Workshop on Algorithms and Data Structures (WADS), Halifax, Nova Scotia, 2007.
