Name
Abstract | ||
|---|---|---|
For decades, the algorithm providing the smallest proven worst-case running time (with respect to the number of terminals) for the Steiner tree problem has been the one by Dreyfus and Wagner. In this paper, a new algorithm is developed, which improves the running time from O(3kn+2kn2+n3) to (2+δ)k ·poly(n) for arbitrary but fixed δ 0. Like its predecessor, this algorithm follows the dynamic programming paradigm. Whereas in effect the Dreyfus–Wagner recursion splits the optimal Steiner tree in two parts of arbitrary sizes, our approach looks for a set of nodes that separate the tree into parts containing only few terminals. It is then possible to solve an instance of the Steiner tree problem more efficiently by combining partial solutions. |
Year | DOI | Venue |
|---|---|---|
2006 | 10.1007/11672142_46 | STACS |
Keywords | Field | DocType |
wagner recursion,steiner tree problem,partial solution,new algorithm,optimal steiner tree,arbitrary size,dynamic programming paradigm,faster algorithm,steiner tree | Discrete mathematics,Dynamic programming,Combinatorics,Tree (graph theory),Steiner tree problem,K-ary tree,Algorithm,Segment tree,Recursion,Mathematics,Interval tree | Conference |
Volume | ISSN | ISBN |
3884 | 0302-9743 | 3-540-32301-5 |
Citations | PageRank | References |
25 | 1.63 | 14 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Daniel Mölle | 1 | 175 | 10.17 |
| Stefan Richter | 2 | 176 | 9.96 |
| Peter Rossmanith | 3 | 1000 | 61.03 |