The Steiner tree problem

zbMath0774.05001MaRDI QIDQ1202044

D. S. Richards, Pawel Winter, Frank K. Hwang

Publication date: 23 January 1993

Published in: Annals of Discrete Mathematics (Search for Journal in Brave)

zbMATH Keywords

Steiner problemminimum spanning treeSteiner treenetwork reliabilityrectilinear Steiner treeefficient algorithmsexact algorithmsdistance metricshortest networkSteiner ratio conjectureEuclidean Steiner problemrectilinear metric

Mathematics Subject Classification ID

Trees (05C05) Research exposition (monographs, survey articles) pertaining to combinatorics (05-02) Graph theory (including graph drawing) in computer science (68R10)

Related Items

DIAMETER-CONSTRAINED STEINER TREES ⋮ Unnamed Item ⋮ The average Steiner 3-eccentricity of block graphs ⋮ Optimum steiner ratio for gradient-constrained networks connecting three points in 3-space, part II: The gradient-constraint m satisfies \documentclass{article} \usepackage{amsmath,amsfonts,amssymb}\pagestyle{empty}\begin{document}$ 1 \leq m \leq \sqrt{3} ⋮ A New Relaxation in Conic Form for the Euclidean Steiner Problem in ℜ ⋮ Generalized XOR non-locality games with graph description on a square lattice ⋮ A survey of combinatorial optimization problems in multicast routing ⋮ Approximation schemes for node-weighted geometric Steiner tree problems ⋮ Computing optimal Steiner trees in polynomial space ⋮ Approximate Euclidean Steiner trees ⋮ The Gilbert arborescence problem ⋮ On a nonconvex MINLP formulation of the Euclidean Steiner tree problem in \(n\)-space: missing proofs ⋮ Steiner 4-diameter, maximum degree and size of a graph ⋮ A Note on the Steinerk-Diameter of Tensor Product Networks ⋮ Extending the kernel for planar Steiner tree to the number of Steiner vertices ⋮ A tutorial on the balanced minimum evolution problem ⋮ On the computational difficulty of the terminal connection problem ⋮ Counting tripods on the torus ⋮ Optimal connected subgraphs: Integer programming formulations and polyhedra ⋮ Stronger path‐based extended formulation for the Steiner tree problem ⋮ Heuristic and exact algorithms for minimum-weight non-spanning arborescences ⋮ An exact branch and bound algorithm for the Steiner Problem in Graphs ⋮ Solving Steiner trees: Recent advances, challenges, and perspectives ⋮ On undirected two‐commodity integral flow, disjoint paths and strict terminal connection problems ⋮ Approximation algorithms for feasible cut and multicut problems ⋮ A massively parallel branch-\&-bound algorithm for the balanced minimum evolution problem ⋮ Geometric dynamics of anchored filamentous networks subject to viscous flow ⋮ Steiner distance and convexity in graphs ⋮ (1 + ρ)-Approximation for Selected-Internal Steiner Minimum Tree ⋮ Reoptimization of Steiner Trees ⋮ Exact and heuristic approaches for the maximum lifetime problem in sensor networks with coverage and connectivity constraints ⋮ Bifurcations of Steiner tree topologies in the plane ⋮ Unnamed Item ⋮ Approximations for two variants of the Steiner tree problem in the Euclidean plane \(\mathbb R^2\) ⋮ Minimum diameter cost-constrained Steiner trees ⋮ Digraph width measures in parameterized algorithmics ⋮ Counterexample to regularity in average-distance problem ⋮ On the edge capacitated Steiner tree problem ⋮ Euclidean Steiner trees optimal with respect to swapping 4-point subtrees ⋮ Modeling hop-constrained and diameter-constrained minimum spanning tree problems as Steiner tree problems over layered graphs ⋮ Faster Steiner Tree Computation in Polynomial-Space ⋮ Sweeping Points ⋮ Strong Steiner Tree Approximations in Practice ⋮ An Efficient Approximation Algorithm for the Steiner Tree Problem ⋮ Reductions for the rectilinear steiner tree problem ⋮ On the average Steiner 3-eccentricity of trees ⋮ The Steiner \(k\)-eccentricity on trees ⋮ Steiner minimal trees in rectilinear and octilinear planes ⋮ Steiner diagrams and \(k\)-star hubs ⋮ Approximation Schemes for Capacitated Geometric Network Design ⋮ Approximation Algorithms for Steiner Tree Based on Star Contractions: A Unified View ⋮ Steiner hull algorithm for the uniform orientation metrics ⋮ Bottleneck Steiner tree with bounded number of Steiner vertices ⋮ Weighted skeletons and fixed-share decomposition ⋮ The Euclidean bottleneck full Steiner tree problem ⋮ Algorithmic aspects of Steiner convexity and enumeration of Steiner trees ⋮ Worst-case performance of Wong's Steiner tree heuristic ⋮ Concurrent multicast in weighted networks ⋮ Variable neighbourhood search for the minimum labelling Steiner tree problem ⋮ Steiner minimal trees for zigzag lines with ladders ⋮ A near linear time approximation scheme for Steiner tree among obstacles in the plane ⋮ Steiner trees and polyhedra ⋮ A comparison of Steiner tree relaxations ⋮ Improved algorithms for the Steiner problem in networks ⋮ COMPUTING STEINER POINTS AND PROBABILITY STEINER POINTS IN ℓ₁ AND ℓ₂ METRIC SPACES ⋮ The sequential sum problem and performance bounds on the greedy algorithm for the on‐line Steiner problem ⋮ Network modelling of underground mine layout: two case studies ⋮ A novel approach to phylogenetic trees: d‐Dimensional geometric Steiner trees ⋮ Approximations for Steiner trees with minimum number of Steiner points ⋮ Wire segmenting for buffer insertion based on RSTP-MSP ⋮ Parameterized Complexity of Directed Steiner Tree on Sparse Graphs ⋮ Implications, conflicts, and reductions for Steiner trees ⋮ The vertex steiner number of a graph ⋮ Average-distance problem for parameterized curves ⋮ Implications, conflicts, and reductions for Steiner trees ⋮ Reorganizing topologies of Steiner trees to accelerate their eliminations ⋮ A multivariate analysis of the strict terminal connection problem ⋮ Approaches to the Steiner Problem in Networks ⋮ Flots entiers et multiflots fractionnaires couplés par une contrainte de capacité ⋮ Complexity of the Steiner Network Problem with Respect to the Number of Terminals ⋮ Iterated local search algorithms for the Euclidean Steiner tree problem inndimensions ⋮ Constrained Steiner trees in Halin graphs ⋮ Unnamed Item ⋮ Shared Multicast Trees in Ad Hoc Wireless Networks ⋮ Generating all the Steiner trees and computing Steiner intervals for a fixed number of terminals ⋮ On Digraph Width Measures in Parameterized Algorithmics ⋮ Towards a lifecycle oriented design of infrastructure by mathematical optimization ⋮ Network optimization for the design of underground mines ⋮ On the Steiner hyper-Wiener index of a graph ⋮ Cost optimisation for underground mining networks ⋮ Parameterized Approximation Schemes for Steiner Trees with Small Number of Steiner Vertices ⋮ Speeding up dynamic programming with representative sets: an experimental evaluation of algorithms for Steiner Tree on tree decompositions ⋮ Isoperimetric enclosures ⋮ On Hop-Constrained Steiner Trees in Tree-Like Metrics ⋮ Maximizing the net present value of a Steiner tree ⋮ On full Steiner trees in unit disk graphs ⋮ Approximation Schemes for Capacitated Geometric Network Design ⋮ Monochromatic geometric \(k\)-factors for bicolored point sets with auxiliary points ⋮ Mathematical optimization ideas for biodiversity conservation ⋮ The Clustered Selected-Internal Steiner Tree Problem ⋮ Geometric Network Creation Games ⋮ Robust capacitated Steiner trees and networks with uniform demands ⋮ O(n log n)-average-time algorithm for shortest network under a given topology ⋮ Steiner problems on directed acyclic graphs ⋮ Ordered scheduling in control-flow distributed transactional memory ⋮ Unnamed Item ⋮ An estimate of the objective function optimum for the network Steiner problem ⋮ Gradient-constrained discounted Steiner trees. I: Optimal tree configurations ⋮ Steiner polygons in the Steiner problem ⋮ On the terminal connection problem ⋮ Steiner tree problem with minimum number of Steiner points and bounded edge-length ⋮ 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 ⋮ New pruning rules for the Steiner tree problem and 2-connected Steiner network problem ⋮ Maximising the worth of nascent networks ⋮ Weighted 2-sections and hypergraph reconstruction ⋮ Short trees in polygons ⋮ A specialized branch-and-bound algorithm for the Euclidean Steiner tree problem in \(n\)-space ⋮ Approximation algorithms for constructing specific subgraphs with minimum number of length-bounded stock pieces ⋮ A better constant-factor approximation for selected-internal Steiner minimum tree ⋮ Cut and patch Steiner trees for ladders ⋮ Enhanced compact models for the connected subgraph problem and for the shortest path problem in digraphs with negative cycles ⋮ Branch-and-price approaches for the network design problem with relays ⋮ Locally minimal uniformly oriented shortest networks ⋮ Minimal Steiner trees for rectangular arrays of lattice points ⋮ Efficiently solvable special cases of hard combinatorial optimization problems ⋮ On the equivalence of the bidirected and hypergraphic relaxations for Steiner tree ⋮ 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 ⋮ A heuristic for the Steiner problem in graphs ⋮ On reductions for the Steiner problem in graphs ⋮ The Steiner tree problem in orientation metrics ⋮ An improved approximation algorithm for the partial-terminal Steiner tree problem with edge cost 1 or 2 ⋮ Risk models for the prize collecting Steiner tree problems with interval data ⋮ Flip distance between triangulations of a simple polygon is NP-complete ⋮ On the approximability of the Steiner tree problem. ⋮ A PTAS for weight constrained Steiner trees in series--parallel graphs. ⋮ Steiner tree reoptimization in graphs with sharpened triangle inequality ⋮ SCIP-Jack -- a solver for STP and variants with parallelization extensions ⋮ The minimum spanning tree problem with conflict constraints and its variations ⋮ Computing Steiner points for gradient-constrained minimum networks ⋮ Solving group Steiner problems as Steiner problems. ⋮ Tree network design avoiding congestion ⋮ New geometry-inspired relaxations and algorithms for the metric Steiner tree problem ⋮ On segmenting logistical zones for servicing continuously developed consumers ⋮ Delay-related secondary objectives for rectilinear Steiner minimum trees. ⋮ The Steiner ratio of high-dimensional Banach--Minkowski spaces. ⋮ A practical algorithm for the minimum rectilinear Steiner tree ⋮ Connectivity calculus ⋮ Steiner's invariants and minimal connections ⋮ Obstacle-aware optimization of offshore wind farm cable layouts ⋮ The neglected pillar of material computation ⋮ A tabu search heuristic for the generalized minimum spanning tree problem ⋮ A primer of the Euclidean Steiner problem ⋮ On the structure and complexity of the 2-connected Steiner network problem in the plane ⋮ Heuristics for automated knowledge source integration and service composition ⋮ 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 ⋮ A series of approximation algorithms for the acyclic directed Steiner tree problem ⋮ An improved algorithm for computing Steiner minimal trees in Euclidean \(d\)-space ⋮ Binary Steiner trees: structural results and an exact solution approach ⋮ On the core and nucleolus of directed acyclic graph games ⋮ Minimal curvature-constrained networks ⋮ The full Steiner tree problem ⋮ Sweeping points ⋮ New formulations for the hop-constrained minimum spanning tree problem via Sherali and Driscoll's tightened Miller-Tucker-Zemlin constraints ⋮ Two variations of the minimum Steiner problem ⋮ The Fermat star of binary trees ⋮ Planar bus graphs ⋮ Steiner diameter, maximum degree and size of a graph ⋮ Minimum diameter vertex-weighted Steiner tree ⋮ Quasi-median hulls in Hamming space are Steiner hulls ⋮ The Steiner problem on surfaces of revolution ⋮ Local search for the Steiner tree problem in the Euclidean plane ⋮ Bifurcations of binary types of Steiner minimal networks in the plane ⋮ 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 ⋮ Insight into the computation of Steiner minimal trees in Euclidean space of general dimension ⋮ Combinatorial optimization in system configuration design ⋮ Computing optimal rectilinear Steiner trees: A survey and experimental evaluation ⋮ Class Steiner trees and VLSI-design ⋮ On approximation algorithms for the terminal Steiner tree problem ⋮ Steiner trees for fixed orientation metrics ⋮ 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 ⋮ Approximation algorithms for constructing required subgraphs using stock pieces of fixed length ⋮ Generalized spanning trees ⋮ Steiner intervals, geodesic intervals, and betweenness ⋮ The dynamic predicate stashing copy problem and the Steiner problem in graphs ⋮ Neural and delay based heuristics for the Steiner problem in networks ⋮ Exploring the constrained maximum edge-weight connected graph problem ⋮ Digital data networks design using genetic algorithms ⋮ 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 ⋮ Distance realization problems with applications to internet tomography ⋮ 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 ⋮ Upper and lower bounding strategies for the generalized minimum spanning tree problem