Saarland University
Department of Computer Science
Computational Complexity
Computational Complexity




Computational Complexity - Research Seminar

Xinhui Wang (University of Twente): Exact Algorithms for the Steiner Tree Problem

Sept. 5, 2008, 10:15 a.m.
E 1 3, Room 415

In this talk, the exact algorithms for the Steiner tree problem will be investigated. The Dreyfus-Wagner algorithm is a well-known dynamic programming method for computing minimum Steiner trees in general weighted graphs in time O(3k), where k is the number of the terminals.

Firstly, two exact algorithms for the Steiner tree problem will be presented. The first one improves the running time of algorithm to O*(2.684k) by showing that the optimum Steiner tree T can be partitioned into T = T1T2T3 in a certain way such that each Ti is a minimum Steiner tree in a suitable contracted graph Gi with less than k/2 terminals. The second algorithm is in time O((2 + δ)k) for any δ > 0.

Every rectilinear Steiner tree problem admits an optimal tree T* which is composed of tree stars. Moreover, the currently fastest algorithm for the rectilinear Steiner tree
problem proceeds by composing an optimum tree T* from tree star components in the cheapest way. Fößmeier and Kaufmann showed that any problem instance with k terminals has a number of tree stars in between 1.32k and 1.38k. We also present additional conditions on tree stars which allow us to further reduce the number of candidate components building the optimum Steiner tree to O(1.337k).