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

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

PDF
Restricted to UT campus only: Request a copy
135Kb

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:	Discrete Mathematics and Mathematical Programming (DMMP)
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

Show download statistics for this publication

Repository Staff Only: item control page