The Number of Tree Stars Is $O^*(1.357^k)$

Fuchs, Bernard and Kern, Walter and Wang, Xinhui (2007) The Number of Tree Stars Is $O^*(1.357^k)$ . Algorithmica, 49 (3). pp. 232-244. ISSN 0178-4617

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

Abstract:	Every rectilinear Steiner tree problem admits an optimal tree $T^$ which is composed of $\emph{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össmeier 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^*(\rho^k)$ where $\rho \approx 1.357$ and mention some consequences of this result.
Item Type:	Article
Copyright:	© 2007 Springer
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/64538
Official URL:	http://dx.doi.org/10.1007/s00453-007-9020-y
Export this item as:	BibTeX EndNote HTML Citation Reference Manager

Show download statistics for this publication

Repository Staff Only: item control page

Metis ID: 245864