<%@ Page Language="C#" MasterPageFile="~/Main.master" AutoEventWireup="true" Title="Volume 6 Issue 3" %>
Embedding Complexity and Discrete Optimization II: A Dynamical Programming Approach to the Steiner-Tree Problem
D. Cieslik1, A. Dress2, K.T. Huber3, and V. Moulton4
1Institute of Mathematics and Computer Science, University of Greifswald, 17487 Greifswald Germany
2FSPM-Strukturbildungsprozesse, University of Bielefeld, 33501 Bielefeld, Germany
3Department of Biometry and Informatics, Swedish University of Agricultural Sciences, 75007 Uppsala, Sweden
4Linnaeus Center for Bioinformatics, Uppsala University, BMC, Box 598, 75124 Uppsala Sweden
Annals of Combinatorics 6 (3) p.275-283 September, 2002
AMS Subject Classification: 90C39, 05C05, 68W99
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 treewidth-based 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.
Keywords: Optimization, discrete optimization, Divide and Conquer, dynamic programming, dynamic-programming schemes, computational complexity, algorithmic complexity, structural complexity, embedding complexity, treewidth, Steiner's problem, Steiner minimal trees, SMT


1. H.J. Bandelt, P. Forster, B.C. Sykes, and M.B. Richards, Mitochondrial portraits of human populations using median networks, Genetics 141 (1995) 743每753.

2. D. Cieslik, Steiner Minimal Trees, Kluwer Academic Publishers, 1998.

3. D. Cieslik, A. Dress, K.T. Huber, and V. Moulton, Embedding complexity and discrete optimization I: a new divide and conquer approach to discrete optimization, Ann. Combin. 6 (2002) 257每273.

4. D. Cieslik, A. Dress, K.T. Huber, and V. Moulton, Connectivity calculus and the Steiner problem, Appl. Math. Lett., to appear.

5. S.E. Dreyfus and R.A. Wagner, The Steiner problem in graphs, Networks 1 (1971/72) 195每 207.

6. S.L. Hakimi, Steiner*s problem in graphs and its implications, Networks 1 (1971/72) 113每 133.

7. F.K. Hwang, D.S. Richards, and P. Winter, The Steiner Tree Problem, North-Holland, 1992.

8. R.M. Karp, Reducibility among combinatorial problems, In: Complexity of Computer Computations, R.E. Miller and J.W. Thatcher, Eds., New York, 1962, pp. 85每103.

9. E.L. Lawler, Combinatorial Optimization Networks and Matroids, Holt, Rinehart and Winston, New York, 1976.

10. S. Raghavan and T.L. Magnanti, Network connectivity, In: Annotated Bibliographies in Combinatorial Optimization, M. Dell*Arnico, F. Maffioli, and S. Martello, Eds., John Wiley & Sons, 1997, pp. 335每354.