Name
Title | ||
|---|---|---|
An efficient polynomial-time approximation scheme for Steiner forest in planar graphs |
Abstract | ||
|---|---|---|
We give an O(n log3 n) approximation scheme for Steiner forest in planar graphs, improving on the previous approximation scheme for this problem, which runs in O(nf(ε)) time. |
Year | DOI | Venue |
|---|---|---|
2012 | 10.5555/2095116.2095169 | symposium on discrete algorithms |
Keywords | DocType | Volume |
steiner forest,approximation scheme,efficient polynomial-time approximation scheme,log3 n,planar graph,previous approximation scheme,polynomial time approximation scheme,data structure | Conference | abs/1110.1320 |
ISBN | Citations | PageRank |
978-1-61197-251-1 | 7 | 0.46 |
References | Authors | |
13 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| David Eisenstat | 1 | 285 | 19.59 |
| Philip N. Klein | 2 | 2681 | 256.19 |
| Claire Mathieu | 3 | 452 | 25.78 |