The rectilinear Steiner arborescence problem

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

zbMATH Keywords

algorithmdirected graphsSteiner treesrectilinear distancerectilinear Steiner arborescence

Mathematics Subject Classification ID

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