The rectilinear Steiner arborescence problem
From MaRDI portal
Publication:1186802
DOI10.1007/BF01758762zbMath0773.05041OpenAlexW1988808425MaRDI QIDQ1186802
Sailesh K. Rao, Ponnuswamy Sadayappan, Frank K. Hwang, Peter W. Shor
Publication date: 28 June 1992
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf01758762
Trees (05C05) Graph theory (including graph drawing) in computer science (68R10) Directed graphs (digraphs), tournaments (05C20)
Related Items (18)
Linear-size planar Manhattan network for convex point sets ⋮ Optimal Competitiveness for the Rectilinear Steiner Arborescence Problem ⋮ Steiner Trees with Bounded RC-Delay ⋮ Embedding rectilinear Steiner trees with length restrictions ⋮ The Rectilinear Steiner Tree Problem with Given Topology and Length Restrictions ⋮ Equispreading tree in Manhattan distance ⋮ Flip distance between triangulations of a simple polygon is NP-complete ⋮ Steiner problems on directed acyclic graphs ⋮ A series of approximation algorithms for the acyclic directed Steiner tree problem ⋮ Approximating the generalized minimum Manhattan network problem ⋮ A catalog of Hanan grid problems ⋮ A rounding algorithm for approximating minimum Manhattan networks ⋮ Steiner trees with bounded RC-delay ⋮ Two variations of the minimum Steiner problem ⋮ Dynamic programming approach to the generalized minimum Manhattan network problem ⋮ A deep-submicron Steiner tree. ⋮ Angle-restricted Steiner arborescences for flow map layout ⋮ Extending the quadrangle inequality to speed-up dynamic programming
Cites Work
- On Steiner trees for bounded point sets
- The shortest path and the shortest road through n points
- On Steiner Minimal Trees with Rectilinear Distance
- Finding optimum branchings
- An O ( n log n ) Algorithm for Rectilinear Minimal Spanning Trees
- The Rectilinear Steiner Tree Problem is $NP$-Complete
- Subclass of the Steiner problems on a plane with rectilinear metric
- Cost-minimal trees in directed acyclic graphs
- On Steiner’s Problem with Rectilinear Distance
This page was built for publication: The rectilinear Steiner arborescence problem
