| Article ID: | iaor2009602 |
| Country: | United States |
| Volume: | 41 |
| Issue: | 3 |
| Start Page Number: | 493 |
| End Page Number: | 500 |
| Publication Date: | Oct 2007 |
| Journal: | Theory of Computing Systems |
| Authors: | Kern W., Wang X., Fuchs B., Moelle D., Richter S., Rossmanith Peter |
| Keywords: | programming: dynamic |
We present a new dynamic programming algorithm that solves the minimum Steiner tree problem on graphs with k terminals in time O* (c(k)) for any c > 2. This improves the running time of the previously fastest parameterized algorithm by Dreyfus–Wagner of order O* (3k) and the so-called ‘full set dynamic programming’ algorithm solving rectilinear instances in time O* (2.3 8(k)).