The Steiner tree problem
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.
- Steiner tree problems
- Steiner tree problems
- The Steiner tree problem and its generalizations
- scientific article; zbMATH DE number 4010182
- The full Steiner tree problem
- scientific article; zbMATH DE number 3871417
- The Steiner connectivity problem
- Solving Steiner tree problems in graphs to optimality
- The 1-steiner tree problem
- A constrained Steiner tree problem
- Quasi-median hulls in Hamming space are Steiner hulls
- Combinatorial optimization in system configuration design
- On approximation algorithms for the terminal Steiner tree problem
- Steiner trees for fixed orientation metrics
- Steiner intervals, geodesic intervals, and betweenness
- Exploring the constrained maximum edge-weight connected graph problem
- A primer of the Euclidean Steiner problem
- Steiner tree problems
- Worst-case minimum rectilinear Steiner trees in all dimensions
- Weighted connected domination and Steiner trees in distance-hereditary graphs
- Minimal binary trees with a regular boundary: The case of skeletons with five endpoints
- Approximations for subset interconnection designs
- Computing optimal rectilinear Steiner trees: A survey and experimental evaluation
- Class Steiner trees and VLSI-design
- The partial sum criterion for Steiner trees in graphs and shortest paths
- On the approximability of the Steiner tree problem in phylogeny
- Minimal connected enclosures on an embedded planar graph
- Neural and delay based heuristics for the Steiner problem in networks
- The Steiner tree problem in Kalmanson matrices and in circulant matrices
- The general Steiner problem in rectangular crisscross space
- Euclidean Steiner minimal trees with obstacles and Steiner visibility graphs
- Steiner polygons in the Steiner problem
- The Steiner ratio
- Short trees in polygons
- Cut and patch Steiner trees for ladders
- Minimal Steiner trees for rectangular arrays of lattice points
- Efficiently solvable special cases of hard combinatorial optimization problems
- The computational complexity of Steiner tree problems in graded matrices
- On finding two-connected subgraphs in planar graphs
- The point-to-point connection problem - analysis and algorithms
- The Steiner tree problem in orientation metrics
- Steiner minimal trees
- On the approximability of the Steiner tree problem.
- A PTAS for weight constrained Steiner trees in series--parallel graphs.
- Solving group Steiner problems as Steiner problems.
- Delay-related secondary objectives for rectilinear Steiner minimum trees.
- The Steiner ratio of high-dimensional Banach--Minkowski spaces.
- Connectivity calculus
- Generalized spanning trees
- The dynamic predicate stashing copy problem and the Steiner problem in graphs
- On the complexity of the Steiner problem
- Digital data networks design using genetic algorithms
- Distance realization problems with applications to internet tomography
- New pruning rules for the Steiner tree problem and 2-connected Steiner network problem
- Approximation algorithms for constructing specific subgraphs with minimum number of length-bounded stock pieces
- Branch-and-price approaches for the network design problem with relays
- SCIP-Jack -- a solver for STP and variants with parallelization extensions
- Obstacle-aware optimization of offshore wind farm cable layouts
- The GeoSteiner software package for computing Steiner trees in the plane: an updated computational study
- Decomposition methods for the two-stage stochastic Steiner tree problem
- Binary Steiner trees: structural results and an exact solution approach
- Minimal curvature-constrained networks
- Two variations of the minimum Steiner problem
- Local search for the Steiner tree problem in the Euclidean plane
- On the location of Steiner points in uniformly-oriented Steiner trees.
- The General Steiner Tree-Star problem.
- Improved methods for approximating node weighted Steiner trees and connected dominating sets.
- Steiner's problem in double trees
- Optimal Steiner hull algorithm
- Planar Manhattan local minimal and critical networks
- Weighted sequence graphs: Boosting iterated dynamic programming using locally suboptimal solutions
- Uncapacitated point-to-multipoint network flow problem and its application to multicasting in telecommunication networks
- On Steiner trees and minimum spanning trees in hypergraphs
- Rotationally optimal spanning and Steiner trees in uniform orientation metrics
- A column generation approach for solving a non-temporal forest harvest model with spatial structure constraints
- A heuristic for the Steiner problem in graphs
- Computing Steiner points for gradient-constrained minimum networks
- A practical algorithm for the minimum rectilinear Steiner tree
- On the structure and complexity of the 2-connected Steiner network problem in the plane
- Steiner diameter, maximum degree and size of a graph
- Minimum diameter vertex-weighted Steiner tree
- Bifurcations of binary types of Steiner minimal networks in the plane
- Insight into the computation of Steiner minimal trees in Euclidean space of general dimension
- Approximation algorithms for constructing required subgraphs using stock pieces of fixed length
- Weighted 2-sections and hypergraph reconstruction
- The average Steiner 3-eccentricity of block graphs
- On a nonconvex MINLP formulation of the Euclidean Steiner tree problem in \(n\)-space: missing proofs
- Heuristic and exact algorithms for minimum-weight non-spanning arborescences
- Bifurcations of Steiner tree topologies in the plane
- On the edge capacitated Steiner tree problem
- On the average Steiner 3-eccentricity of trees
- The Steiner \(k\)-eccentricity on trees
- On the history of the Euclidean Steiner tree problem
- Bottleneck Steiner tree with bounded number of Steiner vertices
- The Euclidean bottleneck full Steiner tree problem
- Algorithmic aspects of Steiner convexity and enumeration of Steiner trees
- Variable neighbourhood search for the minimum labelling Steiner tree problem
- A near linear time approximation scheme for Steiner tree among obstacles in the plane
- A multivariate analysis of the strict terminal connection problem
- Towards a lifecycle oriented design of infrastructure by mathematical optimization
- On the Steiner hyper-Wiener index of a graph
- Optimal interconnection trees in the plane. Theory, algorithms and applications
- Speeding up dynamic programming with representative sets: an experimental evaluation of algorithms for Steiner Tree on tree decompositions
- Isoperimetric enclosures
- Maximizing the net present value of a Steiner tree
- On full Steiner trees in unit disk graphs
- Monochromatic geometric k-factors for bicolored point sets with auxiliary points
- On the clustered Steiner tree problem
- Mathematical optimization ideas for biodiversity conservation
- A survey of combinatorial optimization problems in multicast routing
This page was built for publication: The Steiner tree problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1202044)
