Steiner's problem in double trees

Cieslik D, Dress A, Fitch WM (2002)
Applied Mathematics Letters 15(7): 855-860.

Zeitschriftenaufsatz | Veröffentlicht | Englisch
 
Download
Es wurden keine Dateien hochgeladen. Nur Publikationsnachweis!
Autor*in
Cieslik, Dietmar; Dress, AndreasUniBi; Fitch, Walter M.
Abstract / Bemerkung
Steiner's problem for a set X of vertices contained in a weighted graph G = (V, E, l E --> 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 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 --> 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. (C) 2002 Elsevier Science Ltd. All rights reserved.
Stichworte
discrete optimization; optimization; Steiner's problem; Steiner minimal trees; SMT; double trees; parsimonious trees; dynamic programming; most
Erscheinungsjahr
2002
Zeitschriftentitel
Applied Mathematics Letters
Band
15
Ausgabe
7
Seite(n)
855-860
ISSN
0893-9659
Page URI
https://pub.uni-bielefeld.de/record/1613880

Zitieren

Cieslik D, Dress A, Fitch WM. Steiner's problem in double trees. Applied Mathematics Letters. 2002;15(7):855-860.
Cieslik, D., Dress, A., & Fitch, W. M. (2002). Steiner's problem in double trees. Applied Mathematics Letters, 15(7), 855-860. https://doi.org/10.1016/S0893-9659(02)00053-8
Cieslik, D., Dress, A., and Fitch, W. M. (2002). Steiner's problem in double trees. Applied Mathematics Letters 15, 855-860.
Cieslik, D., Dress, A., & Fitch, W.M., 2002. Steiner's problem in double trees. Applied Mathematics Letters, 15(7), p 855-860.
D. Cieslik, A. Dress, and W.M. Fitch, “Steiner's problem in double trees”, Applied Mathematics Letters, vol. 15, 2002, pp. 855-860.
Cieslik, D., Dress, A., Fitch, W.M.: Steiner's problem in double trees. Applied Mathematics Letters. 15, 855-860 (2002).
Cieslik, Dietmar, Dress, Andreas, and Fitch, Walter M. “Steiner's problem in double trees”. Applied Mathematics Letters 15.7 (2002): 855-860.

Export

Markieren/ Markierung löschen
Markierte Publikationen

Open Data PUB

Web of Science

Dieser Datensatz im Web of Science®

Suchen in

Google Scholar