2005-04: A Faster Algorithm for the Steiner Tree Problem
9 Mar
2005
9 Mar
'05
5:38 p.m.
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)).
7228
Age (days ago)
7228
Last active (days ago)
0 comments
1 participants
participants (1)
-
Volker Stolz