On Steiner’s Problem with Rectilinear Distance

DOI10.1137/0114025zbMath0151.33205OpenAlexW2064086982MaRDI QIDQ5530464

Maurice Hanan

Publication date: 1966

Published in: SIAM Journal on Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/25fd10878fc44c9128fce40c2d08fd64ff8e4fb2

zbMATH Keywords

topology

Related Items (67)

The rectilinear class Steiner tree problem for intervals on two parallel lines ⋮ Rectilinear Steiner Trees in Rectangle Trees ⋮ Two-level rectilinear Steiner trees ⋮ Steiner Trees with Bounded RC-Delay ⋮ A simple proof that the \((n^{2} - 1)\)-puzzle is hard ⋮ HARDNESS AND APPROXIMATION OF OCTILINEAR STEINER TREES ⋮ A rectilinear steiner minimal tree algorithm for convex point sets ⋮ Greedy algorithms for the on-line steiner tree and generalized steiner problems ⋮ Optimal and approximate bottleneck Steiner trees ⋮ The Rectilinear Steiner Tree Problem with Given Topology and Length Restrictions ⋮ Fast heuristic algorithms for rectilinear Steiner trees ⋮ Steiner minimal trees in \(L^ 2_ p\) ⋮ The Steiner tree problem in orientation metrics ⋮ A probably fast, provably optimal algorithm for rectilinear Steiner trees ⋮ The Performance of greedy algorithms for the on-line steiner tree and related problems ⋮ APPROXIMATION ALGORITHMS FOR BUY-AT-BULK GEOMETRIC NETWORK DESIGN ⋮ Extremal networks in $ \lambda$-geometry, where $ \lambda=3,4,6$ ⋮ Approximation algorithms for Steiner forest: An experimental study ⋮ Who witnesses The Witness? Finding witnesses in The Witness is hard and sometimes impossible ⋮ Minimum rectilinear Steiner tree of \(n\) points in the unit square ⋮ Dijkstra meets Steiner: a fast exact goal-oriented Steiner tree algorithm ⋮ SCIP-Jack -- a solver for STP and variants with parallelization extensions ⋮ Unnamed Item ⋮ Watchman routes for lines and line segments ⋮ Rectilinear paths with minimum segment lengths ⋮ A practical algorithm for the minimum rectilinear Steiner tree ⋮ Locating the vertices of a steiner tree in an arbitrary metric space ⋮ Some upper bounds for minimal trees ⋮ Polynomially solvable special cases of the Steiner problem in planar networks ⋮ The role of Steiner hulls in the solution to Steiner tree problems ⋮ An integrated approach to routing and via minimization ⋮ How to find Steiner minimal trees in Euclidean \(d\)-space ⋮ A linear-time algorithm to construct a rectilinear Steiner minimal tree for \(k\)-extremal point sets ⋮ The rectilinear Steiner arborescence problem ⋮ Two new criteria for finding Steiner hulls in Steiner tree problems ⋮ Steiner minimal trees in rectilinear and octilinear planes ⋮ The GeoSteiner software package for computing Steiner trees in the plane: an updated computational study ⋮ Worst-case minimum rectilinear Steiner trees in all dimensions ⋮ PORA: a Physarum-inspired obstacle-avoiding routing algorithm for integrated circuit design ⋮ A heuristic for Euclidean and rectilinear Steiner problems ⋮ COMPUTING THE STRETCH FACTOR AND MAXIMUM DETOUR OF PATHS, TREES, AND CYCLES IN THE NORMED SPACE ⋮ A catalog of Hanan grid problems ⋮ Anchored rectangle and square packings ⋮ THE MINIMUM GUARDING TREE PROBLEM ⋮ On the history of the Euclidean Steiner tree problem ⋮ Minimal surfaces, crystals, shortest networks, and undergraduate research ⋮ Steiner trees with bounded RC-delay ⋮ Worst-case ratios of networks in the rectilinear plane ⋮ The word and geodesic problems in free solvable groups ⋮ Cost-minimal trees in directed acyclic graphs ⋮ A near linear time approximation scheme for Steiner tree among obstacles in the plane ⋮ The local Steiner problem in normed planes ⋮ Computational experiences with the exchange method. Applied to four commonly used partitioning cluster analysis criteria ⋮ Planar bus graphs ⋮ Steiner's problem and fagnano's result on the sphere ⋮ Wire segmenting for buffer insertion based on RSTP-MSP ⋮ Lower bounds for rectilinear Steiner trees in bounded space ⋮ Computing optimal rectilinear Steiner trees: A survey and experimental evaluation ⋮ Steiner trees for fixed orientation metrics ⋮ A polynomial-time optimization algorithm for a rectilinear partitioning problem with applications in VLSI design automation. ⋮ Speeding up dynamic programming with representative sets: an experimental evaluation of algorithms for Steiner Tree on tree decompositions ⋮ Heuristics for the minimum rectilinear Steiner tree problem: New algorithms and a computational study ⋮ A deep-submicron Steiner tree. ⋮ The \(k\)-nearest-neighbor Voronoi diagram revisited ⋮ Steiner's problem in double trees ⋮ Planar Manhattan local minimal and critical networks ⋮ The Steiner Minimal Tree problem in the λ-geometry plane

This page was built for publication: On Steiner’s Problem with Rectilinear Distance