Back to Search
Start Over
The Number of Tree Stars Is O *(1.357 k ).
- Source :
-
Algorithmica . Nov2007, Vol. 49 Issue 3, p232-244. 13p. - Publication Year :
- 2007
-
Abstract
- Abstract   Every rectilinear Steiner tree problem admits an optimal tree T * which is composed of tree stars. Moreover, the currently fastest algorithms for the rectilinear Steiner tree problem proceed by composing an optimum tree T * from tree star components in the cheapest way. The efficiency of such algorithms depends heavily on the number of tree stars (candidate components). F��meier and Kaufmann (Algorithmica 26, 68â99, 2000) showed that any problem instance with k terminals has a number of tree stars in between 1.32 k and 1.38 k (modulo polynomial factors) in the worst case. We determine the exact bound O *(Ï k ) where Ïâ1.357 and mention some consequences of this result. [ABSTRACT FROM AUTHOR]
- Subjects :
- *STEINER systems
*STARS
*ALGORITHMS
*POLYNOMIALS
Subjects
Details
- Language :
- English
- ISSN :
- 01784617
- Volume :
- 49
- Issue :
- 3
- Database :
- Academic Search Index
- Journal :
- Algorithmica
- Publication Type :
- Academic Journal
- Accession number :
- 27099574
- Full Text :
- https://doi.org/10.1007/s00453-007-9020-y