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

Bernard Fuchs, Walter Kern, Xinhui Wang

Research output: Contribution to journalArticleAcademicpeer-review

2 Citations (Scopus)
34 Downloads (Pure)

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.
Original languageUndefined
Pages (from-to)232-244
Number of pages13
JournalAlgorithmica
Volume49
Issue number1/3
DOIs
Publication statusPublished - Nov 2007

Keywords

  • EWI-11581
  • IR-64538
  • METIS-245864

Cite this