Speeding up the Dreyfus-Wagner algorithm for minimum Steiner trees

Bernard Fuchs, Walter Kern, Xinhui Wang

Research output: Contribution to journalArticleAcademicpeer-review

7 Citations (Scopus)
12 Downloads (Pure)

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)$.
Original languageUndefined
Pages (from-to)117-125
Number of pages9
JournalMathematical methods of operations research
Volume66
Issue numberLNCS4549/1
DOIs
Publication statusPublished - Aug 2007

Keywords

  • METIS-241914
  • IR-61920
  • EWI-11081

Cite this