×

Dynamic programming for minimum Steiner trees. (English) Zbl 1148.68038

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})\).

MSC:

68R10 Graph theory (including graph drawing) in computer science
68W25 Approximation algorithms
90C39 Dynamic programming
PDFBibTeX XMLCite
Full Text: DOI Link