Embedding Complexity and Discrete Optimization II: A Dynamical Programming Approach to the Steiner-Tree Problem

D. Cieslik^{1}, A. Dress^{2}, K.T. Huber^{3}, and V. Moulton^{4}

cieslik@mail.uni-greifswald.de

dress@mathematik.uni-bielefeld.de

katharina.huber@bi.slu.se

vincent.moulton@lcb.uu.se

Annals of Combinatorics 6 (3) p.275-283 September, 2002

Abstract:

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.

References:

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.