The Steiner tree problem (Q1202044): Difference between revisions

The Steiner problem is to construct the shortest network connecting a set of (terminal) points, when one is permitted to introduce intermediate (Steiner) points. Steiner problems arise in a rich variety of applications, and different distance metrics lead to a remarkable number of challenging mathematical questions in geometry, combinatorics and topology. The literature on Steiner problems has grown large, and often specialized. The authors have done a remarkable job of bringing out unifying themes, while retaining the flavor of the main threads of research and application. The monograph is divided into four main parts, according to the distance metric employed in the Steiner problem. Part I concerns the original Steiner problem in the (Euclidean) plane, apparently first studied by Fermat. Preliminary notions are well developed for a clear presentation that balances algorithmic and geometric aspects, and applications. Exact algorithms are first discussed. Then exciting recent developments on the Steiner ratio conjecture (concerning the ratio of the length of a Steiner tree to that of a minimum spanning tree) are introduced in a very accessible way. The computational complexity of the Euclidean Steiner problem then motivates an examination of heuristics, and of special cases. Finally, generalizations to \(d\)-dimensional Euclidean space are studied. Part II treats a very different distance metric, the distances on the edges of a graph. Perhaps on this ``Steiner problem on networks'' has there been the largest explosion of specialized exact algorithms, efficient algorithms for special cases, and generalized problems. The presentation is not encyclopedic; rather it extracts a number of main ideas and explores them. The topics covered are similar to those in Part I, but the emphasis is on the combinatorial aspects of the algorithms rather than geometry. The treatment of generalizations in Part II is necessarily short, and as a result a number of applications are dealt with rather quickly. Nevertheless, a number of these applications (such as \(k\)-terminal network reliability, or query optimization in database systems) would each require a monograph of their own to present details. The authors have opted to give a few pointers into such literature; by and large, this approach works well. Part III concerns the rectilinear (or Manhattan) metric, primarily because of its importance in circuit design. The presentation is a good blend of the geometric concepts of Part I and the combinatorial aspects of Part II, but retains its focus on the intended application. Bringing the algorithms and the mathematics to the application in this way results in a very useful synthesis of the literature. Part IV concerns other distance metrics. First, arbitrary metric spaces are examined. Then, a well-studied Steiner problem in phylogenetic trees is introduced. This book is required reading for anyone working on the Steiner problem in one of its many disguises. But it is much more. It is a very readable introduction to an area with elegant mathematics, clever algorithmic ideas, and a remarkable array of applications.