Steiner Minimal Trees
From MaRDI portal
Publication:5542568
DOI10.1137/0116001zbMath0159.22001OpenAlexW2086709935MaRDI QIDQ5542568
Publication date: 1968
Published in: SIAM Journal on Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://semanticscholar.org/paper/46e57939baff2ec484b2e0f5c4b78f9129e710e9
Related Items
Symmetrization theorem of full Steiner trees ⋮ An estimate of the objective function optimum for the network Steiner problem ⋮ Hexagonal coordinate systems and Steiner minimal trees ⋮ Some results on greedy algorithm conjectures ⋮ Variational approach and Steiner minimal trees on four points ⋮ Steiner polygons in the Steiner problem ⋮ A continuous version of a result of Du and Hwang ⋮ The length of an extremal network in a normed space: Maxwell formula ⋮ Steiner tree problem with minimum number of Steiner points and bounded edge-length ⋮ New pruning rules for the Steiner tree problem and 2-connected Steiner network problem ⋮ Steiner minimal trees on sets of four points ⋮ Maximising the worth of nascent networks ⋮ On greedy heuristic for Steiner minimum trees ⋮ On the Steiner ratio in 3-space ⋮ On component-size bounded Steiner trees ⋮ Steiner minimal trees on regular polygons with centre ⋮ A tight lower bound for the Steiner ratio in Minkowski planes ⋮ A Steiner tree associated with three quarks ⋮ Full minimal Steiner trees on lattice sets ⋮ An improved extra-gradient method for minimizing a sum of \(p\)-norms -- a variational inequality approach ⋮ An algorithm for determining an opaque minimal forest of a convex polygon ⋮ The Steiner ratio for the dual normed plane ⋮ On the equivalence of the bidirected and hypergraphic relaxations for Steiner tree ⋮ A decomposition theorem on Euclidean Steiner minimal trees ⋮ Steiner ratio for hyperbolic surfaces. ⋮ Faster geometric \(k\)-point MST approximation ⋮ Fast heuristic algorithms for rectilinear Steiner trees ⋮ The Fermat-Torricelli problem. I: A discrete gradient-method approach ⋮ Non-crossing of plane minimal spanning and minimal T1 networks ⋮ Cost of sequential connection for points in space ⋮ The Steiner problem with edge lengths 1 and 2 ⋮ The Steiner tree problem in orientation metrics ⋮ A fast algorithm for Steiner trees ⋮ Minimum rectilinear Steiner tree of \(n\) points in the unit square ⋮ Colored spanning graphs for set visualization ⋮ A primal-dual algorithm for the generalized prize-collecting Steiner forest problem ⋮ The Steiner problem in phylogeny is NP-complete ⋮ The Steiner ratio of high-dimensional Banach--Minkowski spaces. ⋮ Packing, covering and tiling in two-dimensional spaces ⋮ A fractal shape optimization problem in branched transport ⋮ Analytic formulas for full Steiner trees ⋮ Minimum cost multicast routing using ant colony optimization algorithm ⋮ The Steiner ratio conjecture for six points ⋮ Some upper bounds for minimal trees ⋮ A primer of the Euclidean Steiner problem ⋮ The Steiner ratio for five points ⋮ On Steiner ratio conjectures ⋮ Minimal length tree networks on the unit sphere ⋮ The role of Steiner hulls in the solution to Steiner tree problems ⋮ Steiner minimal trees for three points with one convex polygonal obstacle ⋮ Optimal design of virtual links in AFDX networks ⋮ Numerical calibration of Steiner trees ⋮ Solving a generalized Gauss problem ⋮ A phase-field approximation of the Steiner problem in dimension two ⋮ The Steiner ratio conjecture for cocircular points ⋮ A proof of the Gilbert-Pollak conjecture on the Steiner ratio ⋮ How to find Steiner minimal trees in Euclidean \(d\)-space ⋮ On Steiner minimal trees with \(L_ p\) distance ⋮ Graham's problem on shortest networks for points on a circle ⋮ Steiner minimal trees for a class of zigzag lines ⋮ Two new criteria for finding Steiner hulls in Steiner tree problems ⋮ The GeoSteiner software package for computing Steiner trees in the plane: an updated computational study ⋮ Worst-case minimum rectilinear Steiner trees in all dimensions ⋮ Steiner convex sets and Cartesian product ⋮ Canonical decompositions of piecewise affine mappings, polyhedra-traces, and geometrical variational problems ⋮ An improved algorithm for computing Steiner minimal trees in Euclidean \(d\)-space ⋮ A heuristic for Euclidean and rectilinear Steiner problems ⋮ Opaque sets ⋮ Binary Steiner trees: structural results and an exact solution approach ⋮ Supportability of network cost functions ⋮ Heuristics for the Steiner problem in graphs ⋮ On better heuristics for Steiner minimum trees ⋮ Constrained BV functions on covering spaces for minimal networks and Plateau's type problems ⋮ A partition-based relaxation for Steiner trees ⋮ An entropy regularization technique for minimizing a sum of Tchebycheff norms ⋮ Minimum weight convex Steiner partitions ⋮ The Steiner ratio conjecture of Gilbert-Pollak may still be open ⋮ Steiner minimal trees for bar waves ⋮ Minimum-weight two-connected spanning networks ⋮ Comparison of distances between measures ⋮ Evolutionary model for the Steiner tree problem with flow-dependent weights ⋮ Some remarks on the Steiner problem ⋮ Minimum Steiner trees in normed planes ⋮ The Steiner problem on surfaces of revolution ⋮ Local search for the Steiner tree problem in the Euclidean plane ⋮ Lower bounds for rectilinear Steiner trees in bounded space ⋮ A randomized Delaunay triangulation heuristic for the Euclidean Steiner tree problem in \(\Re ^{d }\) ⋮ Summarizing a set of time series by averaging: from Steiner sequence to compact multiple alignment ⋮ A short proof of a result of Pollak on Steiner minimal trees ⋮ A class of full Steiner minimal trees ⋮ Multi-colored spanning graphs ⋮ Neural and delay based heuristics for the Steiner problem in networks ⋮ Steiner trees in uniformly quasi-bipartite graphs. ⋮ The Steiner ratio conjecture is true for five points ⋮ Euclidean Steiner minimal trees with obstacles and Steiner visibility graphs ⋮ Numerical minimization of geometrical type problems related to calculus of variations ⋮ A linear time algorithm for full Steiner trees ⋮ A variational approach to the Steiner network problem ⋮ A sausage heuristic for Steiner minimal trees in three-dimensional Euclidean space ⋮ A neural network for the Steiner minimal tree problem ⋮ Minimum Steiner trees on a set of concyclic points and their center ⋮ Solving the prize‐collecting Euclidean Steiner tree problem ⋮ A new second‐order conic optimization model for the Euclidean Steiner tree problem in Rd$\mathbb {R}^d$ ⋮ Construction of the developing connecting tree ⋮ A new heuristic for the Euclidean Steiner tree problem in \(\mathbb{R}^n\) ⋮ Steiner subratio of Riemannian manifolds ⋮ Structural properties of minimum multi-source multi-sink Steiner networks in the Euclidean plane ⋮ O(n log n)-average-time algorithm for shortest network under a given topology ⋮ Unnamed Item ⋮ A faster approximation algorithm for the Steiner problem in graphs ⋮ A faster approximation algorithm for the Steiner problem in graphs ⋮ Approximations for Steiner trees with minimum number of Steiner points ⋮ Euclidean Steiner minimal trees, minimum energy configurations, and the embedding problem of weighted graphs in \(E^ 3\) ⋮ VISCOELASTIC PROPERTIES OF NETWORKS ⋮ Connected perimeter of planar sets ⋮ Mixed integer nonlinear optimization models for the Euclidean Steiner tree problem in \(\mathbb{R}^d\) ⋮ From Cost Sharing Mechanisms to Online Selection Problems ⋮ Geometry-experiment algorithm for Steiner minimal tree problem ⋮ The 1-Steiner-Minimal-Tree problem in Minkowski-spaces ⋮ ON THE STEINER RATIO IN $\mathcal{R}_{n}$ ⋮ A New Relaxation in Conic Form for the Euclidean Steiner Problem in ℜ ⋮ A direct solution of allocation problems ⋮ Truly Optimal Euclidean Spanners ⋮ Variational Approximation of Functionals Defined on 1-dimensional Connected Sets: The Planar Case ⋮ Approximate Euclidean Steiner trees ⋮ Approximation algorithm with constant ratio for stochastic prize-collecting Steiner tree problem ⋮ Determining shortest networks in the Euclidean plane ⋮ Terminal embeddings ⋮ The Fermat-Torricelli theorem in convex geometry ⋮ THE UNIFORM ORIENTATION STEINER TREE PROBLEM IS NP-HARD ⋮ A PTAS for the geometric connected facility location problem ⋮ Steiner minimal trees in \(L^ 2_ p\) ⋮ Optimizing access to drinking water in remote areas. Application to Nepal ⋮ Some problems in discrete optimization ⋮ The steiner problem in graphs ⋮ Variational approximation of size-mass energies fork-dimensional currents ⋮ Steiner distance and convexity in graphs ⋮ Minimum-distance zoning in transportation problems ⋮ Classification of metric spaces whose Steiner-Gromov ratio is equal to one ⋮ 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\) ⋮ A New Bound for the Steiner Ratio ⋮ The structure of minimal Steiner trees in the neighborhoods of the lunes of their edges ⋮ Correlation between the norm and the geometry of minimal networks ⋮ Unnamed Item ⋮ Geometric multicut: shortest fences for separating groups of objects in the plane ⋮ A Conjecture of Gilbert and Pollak on Minimal Trees ⋮ Minimal Networks: A Review ⋮ Geometry and topology of local minimal 2-trees ⋮ Steiner Minimal Trees on Zig-Zag Lines ⋮ Counterexample to regularity in average-distance problem ⋮ The 3‐vertex single source Weber location problem ⋮ Euclidean Steiner trees optimal with respect to swapping 4-point subtrees ⋮ A Modica-Mortola approximation for the Steiner problem ⋮ Computing minimum 2‐edge‐connected Steiner networks in the Euclidean plane ⋮ Locating the vertices of a steiner tree in an arbitrary metric space ⋮ Strong Steiner Tree Approximations in Practice ⋮ Shortest directed networks in the plane ⋮ Manifold learning for organizing unstructured sets of process observations ⋮ ON CHARACTERISTIC AREA OF STEINER TREE ⋮ Cache placement in sensor networks under an update cost constraint ⋮ Improved approximation results for the minimum energy broadcasting problem ⋮ On the history of the Euclidean Steiner tree problem ⋮ Construction of the current Steiner network of the second optimality rank ⋮ Algorithmic aspects of Steiner convexity and enumeration of Steiner trees ⋮ Steiner ratio for Hadamard surfaces of curvature at most \(k < 0\) ⋮ Steiner Minimal Tree for Points on a Circle ⋮ Cost-minimal trees in directed acyclic graphs ⋮ A near linear time approximation scheme for Steiner tree among obstacles in the plane ⋮ Local structure of minimal networks in A. D. Alexandrov spaces ⋮ The local Steiner problem in normed planes ⋮ On the restricted 1-Steiner tree problem ⋮ On the solution of the generalized steiner problem by the subgradient method ⋮ Models and branch‐and‐cut algorithms for the Steiner tree problem with revenues, budget and hop constraints ⋮ On motion by curvature of a network with a triple junction ⋮ Unnamed Item ⋮ Unnamed Item ⋮ A Ginzburg-Landau model with topologically induced free discontinuities ⋮ Weber's problem and weiszfeld's algorithm in general spaces ⋮ Steiner's problem and fagnano's result on the sphere ⋮ An evolutionary design of weighted minimum networks for four points in the three-dimensional Euclidean space ⋮ Approximating minimum Steiner point trees in Minkowski planes ⋮ Generalized Maxwell formula for the length of a minimal tree with a given topology ⋮ The big valley conjecture for the flow Steiner tree problem ⋮ Phase field approximations of branched transportation problems ⋮ Approximation algorithms for solving the 1-line Euclidean minimum Steiner tree problem ⋮ The minimal spanning tree and the upper box dimension ⋮ A family of random trees with random edge lengths ⋮ Average-distance problem for parameterized curves ⋮ Reorganizing topologies of Steiner trees to accelerate their eliminations ⋮ Computation of Minimal Length Full Steiner Trees on the Vertices of a Convex Polygon ⋮ Outer linear measure of connected sets via Steiner trees ⋮ Bifurcations of binary types of Steiner minimal networks in the plane ⋮ Partial regularity for the optimal \(p\)-compliance problem with length penalization ⋮ Steiner type ratios of Gromov-Hausdorff space ⋮ An overview of exact algorithms for the Euclidean Steiner tree problem inn-space ⋮ Branched coverings and Steiner ratio ⋮ Insight into the computation of Steiner minimal trees in Euclidean space of general dimension ⋮ Iterated local search algorithms for the Euclidean Steiner tree problem inndimensions ⋮ IDENTIFYING STEINER MINIMAL TREES ON FOUR POINTS IN SPACE ⋮ Multi-level Steiner Trees ⋮ On notions of distortion and an almost minimum spanning tree with constant average distortion ⋮ Generalizations on the parsimony question in evolution ⋮ \(1\)-line minimum rectilinear Steiner trees and related problems ⋮ On the restricted \(k\)-Steiner tree problem ⋮ Steiner Shallow-Light Trees Are Exponentially Lighter than Spanning Ones ⋮ On the Stretch Factor of Polygonal Chains ⋮ Approximation of Length Minimization Problems Among Compact Connected Sets ⋮ Parameterized Approximation Algorithms for Bidirected Steiner Network Problems ⋮ A continuity criterion for Steiner-type ratios in the Gromov-Hausdorff space ⋮ A Hybrid Metaheuristic for Routing on Multicast Networks ⋮ Multi-Level Steiner Trees. ⋮ The plasticity of some mass transportation networks in the three dimensional Euclidean Space
