×

Steiner’s problem in double trees. (English) Zbl 1009.05040

Summary: Steiner’s problem for a set \(X\) of vertices contained in a weighted graph \(G = (V, E, l : E\to \mathbb{R}_{>0})\) is to find a Steiner minimal tree, that is, a shortest connected subgraph of \(G\) containing the elements of \(X\) among its vertices. In general, this problem is \(\mathcal {NP}\)-hard. So, many heuristics have been proposed in this context. In order to compare results derived by such heuristics with provably exact results, and to analyse in detail how Steiner minimal trees change with \(X\) and with the weighting scheme \(l : E\to \mathbb{R}_{>0}\), we have designed a fast exact algorithm which works for a rather special class of graphs, the class of double trees, that is, the products of trees with \(K_2\) (the complete graph with two vertices), yet represents a class of graphs which is intricate enough for the intended explorations.

MSC:

05C05 Trees
90C35 Programming involving graphs or networks
05C35 Extremal problems in graph theory
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Hakimi, S. B., Steiner’s problem in graphs and its implications, Networks, 1, 113-133 (1971) · Zbl 0229.05124
[2] Karp, R. M., Reducibility among combinatorial problems, (Miller, R. E.; Thatcher, J. W., Complexity of Computer Computations (1962)), 85-103, New York · Zbl 0366.68041
[3] Lawler, E. L., Combinatorial Optimization Networks and Matroids (1976), Holt, Rinehart and Winston: Holt, Rinehart and Winston New York · Zbl 0358.68059
[4] Garey, M. R.; Graham, R. L.; Johnson, D. S., The complexity of computing Steiner minimal trees, SIAM J. Appl. Math., 32, 835-859 (1977) · Zbl 0399.05023
[5] Winter, P., Steiner problems in networks: A survey, Networks, 17, 129-167 (1987) · Zbl 0646.90028
[6] Winter, P., Generalized Steiner problem in series-parallel networks, J. of Algorithms, 7, 549-566 (1986) · Zbl 0623.94023
[7] Wald, J. A.; Colbourn, C. J., Steiner trees, partial 2-trees and minimum IFI networks, Networks, 13, 159-167 (1983) · Zbl 0529.68036
[8] Cieslik, D., Steiner Minimal Trees (1998), Kluwer Academic · Zbl 0997.05500
[9] (Du, D. Z.; Smith, J. M.; Rubinstein, J. H., Advances in Steiner Trees (2000), Kluwer Academic) · Zbl 0932.00010
[10] Hwang, F. K.; Richards, D. S.; Winter, P., The Steiner Tree Problem (1992), North-Holland · Zbl 0774.05001
[11] Voß, S., Steiner-Probleme in Graphen (1990), Anton Hain: Anton Hain Frankfurt a.M
[12] Aho, A. V.; Garey, M. R.; Hwang, F. K., Rectilinear Steiner trees: Efficient-special-case-algorithms, Networks, 7, 37-58 (1977) · Zbl 0351.05102
[13] Richards, D. S.; Salowe, J. S., A linear-time algorithm to construct a rectilinear Steiner minimal tree for \(k\)-extremal point sets, Algorithmica, 7, 247-276 (1992) · Zbl 0748.68030
[14] Salowe, J. S.; Warme, D. M., Thirty-five-point rectilinear Steiner minimal trees in a day, Networks, 25, 69-87 (1995) · Zbl 0820.90120
[15] Hanan, M., On Steiners problem with rectilinear distance, SIAM J. Appl. Math., 14, 255-265 (1966) · Zbl 0151.33205
[16] Arnborg, S.; Lagergren, J.; Seese, D., What problems are easy for tree-decomposable graphs, Lecture Notes Computer Science, 317, 38-51 (1988)
[17] Scheffler, P., Die Baumweite von Graphen als ein Maßfür die Kompliziertheit algorithmischer Probleme, RMATH 04/89 (PhD) (1989), Karl-Weierstraß-Institut: Karl-Weierstraß-Institut Berlin · Zbl 0684.68061
[18] D. Cieslik, A. Dress, K.T. Huber and V. Moulton, Embedding Complexity: A New Approach to Discrete Optimization Using Divide & Conquer, Exemplified with the Steiner Tree Problem,; D. Cieslik, A. Dress, K.T. Huber and V. Moulton, Embedding Complexity: A New Approach to Discrete Optimization Using Divide & Conquer, Exemplified with the Steiner Tree Problem, · Zbl 1023.90051
[19] Dreyfus, S. E.; Wagner, R. A., The Steiner problem in graphs, Networks, 1, 195-207 (1972) · Zbl 0229.05125
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.