PUB - Publikationen an der Universität Bielefeld

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.