Name
Abstract | ||
|---|---|---|
The classical Steiner tree problem requires a shortest tree spanning a given vertex subset within a graph GD .V; E/. An important variant is the Steiner tree prob- lem in rectilinear metric. Only recently two algorithms were found which achieve better approximations than the "traditional" one with a factor of 3=2. These algorithms with an approximation ratio of 11=8 are quite slow and run in time O.n3/ and O.n5=2/ .An ew simple implementation reduces the time to O.n3=2/. As our main result we present efficient parametrized algorithms which reach a performance ratio of 11=8C" for any "> 0 in time O.n¢ log2 n/, and a ratio of 11=8C log log n=log n in time O.n¢ log3 n/. |
Year | DOI | Venue |
|---|---|---|
1997 | 10.1007/PL00009310 | Discrete & Computational Geometry |
Keywords | Field | DocType |
steiner tree problem | Discrete mathematics,Approximation algorithm,Combinatorics,k-minimum spanning tree,Steiner tree problem,Rectilinear Steiner tree,Mathematics,Minimum spanning tree | Journal |
Volume | Issue | ISSN |
18 | 1 | 0179-5376 |
ISBN | Citations | PageRank |
3-540-57568-5 | 7 | 0.91 |
References | Authors | |
9 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Ulrich Fößmeier | 1 | 215 | 17.25 |
| Michael Kaufmann | 2 | 361 | 25.45 |
| Alexander Zelikovsky | 3 | 1691 | 244.62 |