Rectilinear steiner trees: Efficient special-case algorithms

DOI10.1002/net.3230070104zbMath0351.05102OpenAlexW2168570149MaRDI QIDQ4120589

A. V. Aho, Michael R. Garey, Frank K. Hwang

Publication date: 1977

Published in: Networks (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/net.3230070104

Mathematics Subject Classification ID

Trees (05C05)

Related Items (18)

The rectilinear class Steiner tree problem for intervals on two parallel lines ⋮ Rectilinear Steiner Trees in Rectangle Trees ⋮ The Steiner tree problem. I: Formulations, compositions and extensions and extension of facets ⋮ A rectilinear steiner minimal tree algorithm for convex point sets ⋮ Two probabilistic results on rectilinear Steiner trees ⋮ Fixed-parameter algorithms for rectilinear Steiner tree and rectilinear traveling salesman problem in the plane ⋮ Fast heuristic algorithms for rectilinear Steiner trees ⋮ The Steiner tree problem in orientation metrics ⋮ A probably fast, provably optimal algorithm for rectilinear Steiner trees ⋮ Unnamed Item ⋮ Minimizing path lengths in rectilinear Steiner minimum trees with fixed topology ⋮ The role of Steiner hulls in the solution to Steiner tree problems ⋮ 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 ⋮ Two new criteria for finding Steiner hulls in Steiner tree problems ⋮ The point-to-point delivery and connection problems: Complexity and algorithms ⋮ The computation of nearly minimal Steiner trees in graphs ⋮ Steiner's problem in double trees

This page was built for publication: Rectilinear steiner trees: Efficient special-case algorithms