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

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:	Discrete Mathematics and Mathematical Programming (DMMP)
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

Show download statistics for this publication

Repository Staff Only: item control page

Metis ID: 247088