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 (only showing first 100 items - show all)

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 ⋮ An estimate of the objective function optimum for the network Steiner problem

This page was built for publication: The Steiner tree problem