The number of tree stars is O*(1.357k)

Share/Save/Bookmark

Fuchs, Bernard and Kern, Walter and Wang, Xinhui (2006) The number of tree stars is O*(1.357k). Electronic Notes in Discrete Mathematics, 25 . pp. 183-185. ISSN 1571-0653

[img] PDF
Restricted to UT campus only
: Request a copy
138kB
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 [U. Fößmeier, M. Kaufmann, On exact solutions for the rectilinear Steiner tree problem Part 1: Theoretical results, Algorithmica 26 (2000) 68–99] showed that any problem instance with k terminals has a number of tree stars in between 1.32k and 1.38k (modulo polynomial factors) in the worst case. We determine the exact bound of O∗(αk) where α≈1.357 and mention some consequences of this result.
Item Type:Article
Copyright:© 2006 Elsevier
Faculty:
Electrical Engineering, Mathematics and Computer Science (EEMCS)
Research Group:
Link to this item:http://purl.utwente.nl/publications/78471
Official URL:http://dx.doi.org/10.1016/j.endm.2006.06.070
Export this item as:BibTeX
EndNote
HTML Citation
Reference Manager

 

Repository Staff Only: item control page