| Steiner tree in planar graphs: An O(n log n) approximation scheme with singly exponential dependence on epsilon (2007) | |||||||||||||||
Abstract | |||||||||||||||
| Abstract. We give an algorithm that, for any ɛ>0, any undirected planar graph G,andanysetS of nodes of G, computes a (1+ɛ)-optimal Steiner tree in G that spans the nodes of S. The algorithm takes time O(2 poly(1/ɛ) n log n). 1 | |||||||||||||||
Details der Publikation | |||||||||||||||
| |||||||||||||||