9 Mär
2005
9 Mär
'05
17:38
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)).