A proof of the Gilbert-Pollak conjecture on the Steiner ratio
From MaRDI portal
Publication:1186792
DOI10.1007/BF01758755zbMath0774.05027OpenAlexW2024833542WikidataQ123287645 ScholiaQ123287645MaRDI QIDQ1186792
Publication date: 28 June 1992
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf01758755
Related Items (41)
Steiner tree problem with minimum number of Steiner points and bounded edge-length ⋮ On greedy heuristic for Steiner minimum trees ⋮ 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} ⋮ Steiner minimal trees on regular polygons with centre ⋮ A tight lower bound for the Steiner ratio in Minkowski planes ⋮ On spanning 2-trees in a graph ⋮ Approximation schemes for node-weighted geometric Steiner tree problems ⋮ The Steiner ratio for the dual normed plane ⋮ Non-crossing of plane minimal spanning and minimal T1 networks ⋮ An average case analysis of a greedy algorithm for the on-line Steiner tree problem ⋮ A PTAS for the geometric connected facility location problem ⋮ A new heuristic for the Euclidean Steiner tree problem in \(\mathbb{R}^n\) ⋮ The Steiner ratio Gilbert-Pollak conjecture is still open ⋮ O(n log n)-average-time algorithm for shortest network under a given topology ⋮ On minimally \(k\)-edge-connected graphs and shortest \(k\)-edge-connected Steiner networks ⋮ Approximations for two variants of the Steiner tree problem in the Euclidean plane \(\mathbb R^2\) ⋮ Smoothed analysis of partitioning algorithms for Euclidean functionals ⋮ Minimal Networks: A Review ⋮ The Steiner ratio of high-dimensional Banach--Minkowski spaces. ⋮ Packing, covering and tiling in two-dimensional spaces ⋮ A primer of the Euclidean Steiner problem ⋮ On the structure and complexity of the 2-connected Steiner network problem in the plane ⋮ ON CHARACTERISTIC AREA OF STEINER TREE ⋮ Canonical decompositions of piecewise affine mappings, polyhedra-traces, and geometrical variational problems ⋮ A simple proof of the planar rectilinear Steiner ratio ⋮ Localization of minimax points ⋮ Reducing the Steiner problem in four uniform orientations ⋮ Two-connected Steiner networks: structural properties ⋮ Minimum weight convex Steiner partitions ⋮ The Steiner ratio conjecture of Gilbert-Pollak may still be open ⋮ 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\) ⋮ Generalized Maxwell formula for the length of a minimal tree with a given topology ⋮ Minimum Steiner trees in normed planes ⋮ Minimizing Piecewise-Concave Functions Over Polyhedra ⋮ Steiner type ratios of Gromov-Hausdorff space ⋮ Branched coverings and Steiner ratio ⋮ A randomized Delaunay triangulation heuristic for the Euclidean Steiner tree problem in \(\Re ^{d }\) ⋮ On approximation ratios of minimum-energy multicast routing in wireless networks ⋮ The Steiner Minimal Tree problem in the λ-geometry plane ⋮ A sausage heuristic for Steiner minimal trees in three-dimensional Euclidean space
Cites Work
- The Steiner ratio conjecture is true for five points
- The Steiner ratio conjecture for six points
- Some remarks on the Steiner problem
- A New Bound for the Steiner Ratio
- On Steiner Minimal Trees with Rectilinear Distance
- A Lower Bound for the Steiner Tree Problem
- The Complexity of Computing Steiner Minimal Trees
- Steiner Minimal Trees
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: A proof of the Gilbert-Pollak conjecture on the Steiner ratio
