Fuchs, B.; Kern, W.; Molle, D.; Richter, S.; Rossmanith, P.; Wang, X. Dynamic programming for minimum Steiner trees. (English) Zbl 1148.68038 Theory Comput. Syst. 41, No. 3, 493-500 (2007). Summary: 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})\). Cited in 23 Documents MSC: 68R10 Graph theory (including graph drawing) in computer science 68W25 Approximation algorithms 90C39 Dynamic programming Keywords:full set dynamic programming PDFBibTeX XMLCite \textit{B. Fuchs} et al., Theory Comput. Syst. 41, No. 3, 493--500 (2007; Zbl 1148.68038) Full Text: DOI Link