Dynamic Programming for Minimum Steiner Trees

Fuchs, Bernhard and Kern, Walter and Mölle, Daniel and Richter, Stefan and Rossmanith, Peter and Wang, Xinhui (2007) Dynamic Programming for Minimum Steiner Trees.
Published in: Theory of Computing Systems Vol. 41 (3). pp. 493-500.


We present a new dynamic programming algorithm that solves minimum Steiner tree problems with k terminals in time O^*(c^k) for any c>2 . This improves the running time of the previously fastest exponential time algorithms (Dreyfus-Wagner cite{DW}) of order O^*(3^k) and the so-called ''full set dynamic programming" algorithm, cf. cite{FK}, solving rectilinear instances in time O^*(2.38^k) .

Download: [img] Postscript - Preprinted Version
Download (289kB) | Preview
Download: [img] PDF - Preprinted Version
Download (168kB) | Preview
Editorial actions: View Item View Item (Login required)
Deposit Information:
ZAIK Number: zaik2005-492
Depositing User: Bernhard Fuchs
Date Deposited: 12 Dec 2007 00:00
Last Modified: 09 Jan 2012 16:46
URI: http://e-archive.informatik.uni-koeln.de/id/eprint/492