Name
Title | ||
|---|---|---|
Steiner tree in planar graphs: an O(n log n) approximation scheme with singly-exponential dependence on epsilon |
Abstract | ||
|---|---|---|
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). |
Year | DOI | Venue |
|---|---|---|
2007 | 10.1007/978-3-540-73951-7_25 | WADS |
Keywords | Field | DocType |
singly-exponential dependence,approximation scheme,undirected planar graph,time o,n log n,optimal steiner tree,planar graph,steiner tree | Discrete mathematics,Combinatorics,Exponential function,k-minimum spanning tree,Steiner tree problem,Time complexity,Gomory–Hu tree,Mathematics,Planar graph | Conference |
Volume | ISSN | ISBN |
4619 | 0302-9743 | 3-540-73948-3 |
Citations | PageRank | References |
18 | 0.68 | 23 |
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 |