Dynamic programming for minimum steiner trees

Share/Save/Bookmark

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
180Kb
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
Faculty:
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
EndNote
HTML Citation
Reference Manager

 

Repository Staff Only: item control page

Metis ID: 247088