AIB 2005-04: A Faster Algorithm for the Steiner Tree Problem

The following technical report is available from http://aib.informatik.rwth-aachen.de/: Daniel Mölle, Stefan Richter, Peter Rossmanith: A Faster Algorithm for the Steiner Tree Problem AIB 2005-04 The best algorithm for the Steiner tree problem by Dreyfus and Wagner is 33 years old. We celebrate this occasion and present a variation on this theme. A new algorithm is developed, which improves the running time from O(3^k n^3) to O((2+epsilon)^k poly(n)).