Dynamic programming for minimum steiner trees

B. Fuchs, Walter Kern, D. Mölle, S. Richter, P. Rossmanith, Xinhui Wang

Research output: Contribution to journalArticleAcademicpeer-review

40 Citations (Scopus)

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)$.
Original languageUndefined
Pages (from-to)493-500
Number of pages8
JournalTheory of computing systems
Volume41
Issue number3
DOIs
Publication statusPublished - Oct 2007

Keywords

  • EWI-11582
  • IR-62058
  • METIS-247088

Cite this