Improved Computation of Optimal Rectilinear Steiner Minimal Trees
| Autor: | Joseph L. Ganley, James P. Cohoon |
|---|---|
| Rok vydání: | 1997 |
| Předmět: |
Discrete mathematics
Applied Mathematics Computation Steiner tree problem Theoretical Computer Science Dynamic programming Computational Mathematics symbols.namesake Computational Theory and Mathematics Simple (abstract algebra) TheoryofComputation_ANALYSISOFALGORITHMSANDPROBLEMCOMPLEXITY symbols Geometry and Topology Steiner minimal tree Mathematics |
| Zdroj: | International Journal of Computational Geometry & Applications. :457-472 |
| ISSN: | 1793-6357 0218-1959 |
| DOI: | 10.1142/s0218195997000272 |
| Popis: | This paper presents two new algorithms for computing optimal rectilinear Steiner minimal trees. The first algorithm is a simple, easily implemented dynamic programming algorithm that computes an optimal rectilinear Steiner minimal tree on n points in O(n3n) time. The second algorithm improves upon the first using the concept of full-set screening and runs in at most O(n22.62n) time. The analysis of the second algorithm includes a proof that there are at most O(n 1.62n) full sets on n terminals. For instances small enough to practically solve, these time bounds are provably better than the best known bounds of any previous algorithm. Experimental evidence is presented that demonstrates that the algorithms are fast in practice as well. The paper also includes a brief survey of previous algorithms for computing optimal rectilinear Steiner minimal trees. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|