No label defined (Q4247448)

In the last years Steiner minimal trees were becoming an interesting object of research in combinatorial optimization and graph theory. Several authors already published monographs about this problem [\textit{S. Voß}, Steiner-Probleme in Graphen (1990; Zbl 0733.05049), \textit{F. K. Hwan}, \textit{D. S. Richards} and \textit{P. Winter} ``The Steiner tree problem'' (1992; Zbl 0774.05001), \textit{D. Cieslik} ``Steiner Minimal Trees'', Kluwer (1998)]. Now also a special chapter in the Handbook of Combinatorial Optimization deals with the Steiner minimal trees. In the introduction the author writes: ``This paper concentrates on the Steiner Minimal Tree problem, henceforth referred to as the SMT problem. We present several algorithms for calculating Steiner Minimal Trees, including the first parallel algorithm for doing so. Several implementation issues are discussed, some new results are presented, and several ideas for future are proposed. In Section 2 we review the first fundamental algorithm for calculating SMT's. In Section 3 we present a proposed heuristic for SMT's. In Section 4 problem decomposition for SMT's is outlined. In Section 5 we present Winter's sequential algorithm which has been the basis for most computerized calculation of SMT's to the present day. In Section 6 we present a parallel algorithm for SMT's. Extraction of the correct answer is discussed in Section 7. Computational Results are presented in Section 8 and Future Work and open problems are presented in Section 9''. For the entire collection see [Zbl 0914.90001].