On Steiner Minimal Trees with Rectilinear Distance

DOI10.1137/0130013zbMath0322.05101OpenAlexW2069712919WikidataQ56288515 ScholiaQ56288515MaRDI QIDQ4083448

Frank K. Hwang

Publication date: 1976

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

Full work available at URL: https://doi.org/10.1137/0130013

Mathematics Subject Classification ID

Trees (05C05)

Related Items (62)

Rectilinear Steiner Trees in Rectangle Trees ⋮ The Steiner tree problem. I: Formulations, compositions and extensions and extension of facets ⋮ Steiner Trees with Bounded RC-Delay ⋮ On component-size bounded Steiner trees ⋮ A tight lower bound for the Steiner ratio in Minkowski planes ⋮ Two probabilistic results on rectilinear Steiner trees ⋮ The Steiner ratio for the dual normed plane ⋮ Fast heuristic algorithms for rectilinear Steiner trees ⋮ A heuristic for the Steiner problem in graphs ⋮ The Steiner problem with edge lengths 1 and 2 ⋮ Steiner minimal trees in \(L^ 2_ p\) ⋮ The repeater tree construction problem ⋮ The Steiner tree problem in orientation metrics ⋮ A probably fast, provably optimal algorithm for rectilinear Steiner trees ⋮ Extremal networks in $ \lambda$-geometry, where $ \lambda=3,4,6$ ⋮ A fast algorithm for Steiner trees ⋮ Minimum rectilinear Steiner tree of \(n\) points in the unit square ⋮ Dijkstra meets Steiner: a fast exact goal-oriented Steiner tree algorithm ⋮ Swap-vertex based neighborhood for Steiner tree problems ⋮ Ordered scheduling in control-flow distributed transactional memory ⋮ Unnamed Item ⋮ Comments on Bern's probabilistic results on rectilinear Steiner trees ⋮ Minimizing path lengths in rectilinear Steiner minimum trees with fixed topology ⋮ Minimal Networks: A Review ⋮ A tight worst case bound for the performance ratio of heuristics for the minimum rectilinear Steiner tree problem ⋮ Locating the vertices of a steiner tree in an arbitrary metric space ⋮ Routing in VLSI-layout ⋮ On Steiner ratio conjectures ⋮ A simple proof of Hwang's theorem for rectilinear Steiner minimal trees ⋮ An integrated approach to routing and via minimization ⋮ The number of tree stars is \(O^{*}(1.357^k)\) ⋮ A proof of the Gilbert-Pollak conjecture on the Steiner ratio ⋮ On Steiner minimal trees with \(L_ p\) distance ⋮ A linear-time algorithm to construct a rectilinear Steiner minimal tree for \(k\)-extremal point sets ⋮ The rectilinear Steiner arborescence problem ⋮ Speeding up the Dreyfus-Wagner algorithm for minimum Steiner trees ⋮ Worst-case minimum rectilinear Steiner trees in all dimensions ⋮ COMPUTING THE STRETCH FACTOR AND MAXIMUM DETOUR OF PATHS, TREES, AND CYCLES IN THE NORMED SPACE ⋮ A catalog of Hanan grid problems ⋮ On better heuristics for Steiner minimum trees ⋮ A simple proof of the planar rectilinear Steiner ratio ⋮ Steiner trees with bounded RC-delay ⋮ Worst-case ratios of networks in the rectilinear plane ⋮ A near linear time approximation scheme for Steiner tree among obstacles in the plane ⋮ Bounding the expected number of rectilinear full Steiner trees ⋮ Wire segmenting for buffer insertion based on RSTP-MSP ⋮ On approximations for constructing 1-line minimum rectilinear Steiner trees in the Euclidean plane \(\mathbb{R}^2\) ⋮ Minimum Steiner trees in normed planes ⋮ Lower bounds for rectilinear Steiner trees in bounded space ⋮ Steiner type ratios of Gromov-Hausdorff space ⋮ Branched coverings and Steiner ratio ⋮ Computing optimal rectilinear Steiner trees: A survey and experimental evaluation ⋮ Steiner trees for fixed orientation metrics ⋮ On shortest three-edge-connected Steiner networks with Euclidean distance ⋮ Fixed topology Steiner trees and spanning forests ⋮ \(1\)-line minimum rectilinear Steiner trees and related problems ⋮ Approximation algorithms for solving the line-capacitated minimum Steiner tree problem ⋮ The computation of nearly minimal Steiner trees in graphs ⋮ Heuristics for the minimum rectilinear Steiner tree problem: New algorithms and a computational study ⋮ The number of tree stars is O*(1.357k) ⋮ Planar Manhattan local minimal and critical networks ⋮ The Steiner Minimal Tree problem in the λ-geometry plane

This page was built for publication: On Steiner Minimal Trees with Rectilinear Distance