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

Fuchs, Bernhard and Kern, Walter and Wang, Xinhui (2007) The number of tree stars is O^*(1.357^k).
Published in: Algorithmica Vol. 49 (3). pp. 232-244.


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). Foessmeier and Kaufmann 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^*( ho^k) where ho approx 1.357 and mention some consequences of this result.

Download: [img] Postscript - Preprinted Version
Download (505kB) | Preview
Download: [img] PDF - Preprinted Version
Download (193kB) | Preview
Editorial actions: View Item View Item (Login required)
Deposit Information:
ZAIK Number: zaik2007-536
Depositing User: Bernhard Fuchs
Date Deposited: 11 Nov 2007 00:00
Last Modified: 09 Jan 2012 16:37