Embedding complexity and discrete optimization II: A dynamical programming approach to the Steiner-Tree Problem

D. Cieslik, A. Dress, K. T. Huber, V. Moulton

Research output: Contribution to journalArticlepeer-review


In this note, we continue our work devoted to investigating the concept of embedding complexity (cf. Cieslik et al. [3]) and present a new Divide and Conquer algorithm for solving the Steiner-tree problem for graphs that relies on dynamic-programming schemes. In this way,we show how the rather general conceptual framework developed in our previous paper can be used even in rather awkward situations and that, more specifically, it allows us to design a treewidthbased algorithm for finding Steiner trees in a (weighted or unweighted) graph that is linear with respect to the number of the graph's vertices, yet (as we cannot avoid paying the "standard fine" set on using treewidth-based algorithms) highly exponential with respect to the graph's treewidth.
Original languageEnglish
Pages (from-to)275-283
Number of pages9
JournalAnnals of Combinatorics
Issue number3-4
Publication statusPublished - 2002

Cite this