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). |
Year | DOI | Venue |
---|---|---|
2009 | 10.1145/1541885.1541892 | ACM Transactions on Algorithms |
Keywords | Field | DocType |
polynomial-time approximation scheme,steiner tree problem,additional key words and phrases: steiner tree,approximation scheme,planar graph,planar graphs,n log n,steiner tree,polynomial time approximation scheme | Discrete mathematics,Combinatorics,Steiner tree problem,k-minimum spanning tree,Time complexity,Gomory–Hu tree,Mathematics,Planar graph | Journal |
Volume | Issue | ISSN |
5 | 3 | 1549-6325 |
Citations | PageRank | References |
40 | 1.21 | 32 |
Authors | ||
3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Glencora Borradaile | 1 | 275 | 21.24 |
Philip N. Klein | 2 | 2681 | 256.19 |
Claire Mathieu | 3 | 452 | 25.78 |