Speeding up the Dreyfus-Wagner algorithm for minimum Steiner trees

Fuchs, Bernard and Kern, Walter and Wang, Xinhui (2007) Speeding up the Dreyfus-Wagner algorithm for minimum Steiner trees. Mathematical methods of operations research, 66 (1). pp. 117-125. ISSN 1432-2994

PDF
Restricted to UT campus only: Request a copy
147Kb

Abstract:	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_1 \cup 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 ${k\over 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)$ .
Item Type:	Article
Copyright:	© 2007 Springer
Faculty:	Electrical Engineering, Mathematics and Computer Science (EEMCS)
Research Group:	Discrete Mathematics and Mathematical Programming (DMMP)
Link to this item:	http://purl.utwente.nl/publications/61920
Official URL:	http://dx.doi.org/10.1007/s00186-007-0146-0
Export this item as:	BibTeX EndNote HTML Citation Reference Manager

Show download statistics for this publication

Repository Staff Only: item control page

Metis ID: 241914