scientific article; zbMATH DE number 1302181
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].
- Exact computation of Steiner minimal trees in the plane
- A parallel algorithm for computing Steiner trees in strongly chordal graphs
- On Steiner trees and minimum spanning trees in hypergraphs
- Insight into the computation of Steiner minimal trees in Euclidean space of general dimension
- Experimental evaluation of a partitioning algorithm for the steiner tree problem in R2 and R3
- scientific article; zbMATH DE number 1161295 (Why is no real title available?)
- scientific article; zbMATH DE number 874212 (Why is no real title available?)
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4247448)
