Dynamic programming for minimum steiner trees


Fuchs, B. and Kern, W. and Mölle, D. and Richter, S. and Rossmanith, P. and Wang, X. (2007) Dynamic programming for minimum steiner trees. Theory of Computing Systems, 41 (3). pp. 493-500. ISSN 1432-4350

[img] PDF
Restricted to UT campus only
: Request a copy
Abstract: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^*(3^k)$ and the so-called "full set dynamic programming" algorithm solving rectilinear instances in time $O^*(2.38^k)$.
Item Type:Article
Copyright:© 2007 Springer
Electrical Engineering, Mathematics and Computer Science (EEMCS)
Research Group:
Link to this item:http://purl.utwente.nl/publications/62058
Official URL:http://dx.doi.org/10.1007/s00224-007-1324-4
Export this item as:BibTeX
HTML Citation
Reference Manager


Repository Staff Only: item control page

Metis ID: 247088