Abstract | ||
---|---|---|
We give a fundamental result on the location of Steiner points for Steiner minimum trees in uniform orientation metrics. As a corollary we obtain a linear time algorithm for constructing a Steiner minimum tree for a given full topology when the number of uniform orientations is λ = 3m, m ≥ 1. |
Year | DOI | Venue |
---|---|---|
2002 | 10.1016/S0020-0190(02)00208-9 | Inf. Process. Lett. |
Keywords | Field | DocType |
full topology,linear time algorithm,steiner point,uniformly-oriented steiner tree,steiner minimum tree,uniform orientation,uniform orientation metrics,fundamental result,computational geometry,steiner trees,steiner tree | Discrete mathematics,Combinatorics,Steiner tree problem,Computational geometry,Time complexity,Corollary,Mathematics | Journal |
Volume | Issue | ISSN |
83 | 5 | 0020-0190 |
Citations | PageRank | References |
4 | 0.66 | 2 |
Authors | ||
3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Benny K. Nielsen | 1 | 72 | 5.35 |
Pawel Winter | 2 | 99 | 12.98 |
Martin Zachariasen | 3 | 343 | 29.69 |