Speeding up the Dreyfus-Wagner Algorithm for minimum Steiner trees

Fuchs, Bernhard and Kern, Walter and Wang, Xinhui (2007) Speeding up the Dreyfus-Wagner Algorithm for minimum Steiner trees.
Published in: Mathematical Methods of Operations Research Vol. 66 (1). pp. 117-125.


The Dreyfus-Wagner algorithm is a well-known dynamic programming method for computing minimum Steiner trees in general weighted graphs in time O^*(3^k) , where k is the number of terminal nodes to be connected. We improve its running time to O^*(2.684^k) by showing that the optimum Steiner tree T can be partitioned into T=T_1cup T_2 cup T_3 in a certain way such that each T_i is a minimum Steiner tree in a suitable contracted graph G_i with less than frac{k}{2} terminals. In the rectilinear case, there exists a variant of the dynamic programming method that runs in O^*(2.386^k) . In this case, our splitting technique yields an improvement to O^*(2.335^k) .

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