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

Bernard Fuchs, Walter Kern, Xinhui Wang

Research output: Contribution to journalArticleAcademic

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.
Original languageUndefined
Pages (from-to)183-185
JournalElectronic notes in discrete mathematics
Volume25
DOIs
Publication statusPublished - 2006

Keywords

  • Terminal points
  • Rectilinear Steiner tree
  • Tree star
  • Components
  • IR-78471

Cite this