Abstract
We present a new dynamic programming algorithm that solves the minimum Steiner tree problem on graphs with k terminals in time O*(ck) 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.38k).
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Fuchs, B., Kern, W., Molle, D. et al. Dynamic Programming for Minimum Steiner Trees. Theory Comput Syst 41, 493–500 (2007). https://doi.org/10.1007/s00224-007-1324-4
Issue Date:
DOI: https://doi.org/10.1007/s00224-007-1324-4