The rectilinear Steiner arborescence problem

DOI10.1007/BF01758762MaRDI QIDQ1186802zbMATH OpenOpenAlexFDO

Authors Sailesh K. Rao, P. 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) Directed graphs (digraphs), tournaments (05C20) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Optimal competitiveness for the rectilinear Steiner arborescence problem
• The Rectilinear Steiner Arborescence Problem Is NP-Complete
• scientific article; zbMATH DE number 1445377
• Polynomial time approximation scheme for the rectilinear Steiner arborescence problem
• Subexponential algorithms for rectilinear Steiner tree and arborescence problems

Cites work

• An O ( n log n ) Algorithm for Rectilinear Minimal Spanning Trees
• Cost-minimal trees in directed acyclic graphs
• Finding optimum branchings
• On Steiner Minimal Trees with Rectilinear Distance
• On Steiner trees for bounded point sets
• On Steiner’s Problem with Rectilinear Distance
• Subclass of the Steiner problems on a plane with rectilinear metric
• The Rectilinear Steiner Tree Problem is $NP$-Complete
• The shortest path and the shortest road through n points

Cited in

(26)

• Steiner trees with bounded RC-delay
• Linear-size planar Manhattan network for convex point sets
• A deep-submicron Steiner tree.
• Subexponential algorithms for rectilinear Steiner tree and arborescence problems
• Subexponential algorithms for rectilinear Steiner tree and arborescence problems
• Two variations of the minimum Steiner problem
• Logic Programming
• A series of approximation algorithms for the acyclic directed Steiner tree problem
• Polynomial time approximation scheme for the rectilinear Steiner arborescence problem
• Approximating the generalized minimum Manhattan network problem
• Angle-restricted Steiner arborescences for flow map layout
• Angle-Restricted Steiner Arborescences for Flow Map Layout
• scientific article; zbMATH DE number 1445377 (Why is no real title available?)
• Steiner problems on directed acyclic graphs
• Equispreading tree in Manhattan distance
• Reductions for the rectilinear steiner tree problem
• A rounding algorithm for approximating minimum Manhattan networks
• Extending the quadrangle inequality to speed-up dynamic programming
• Dynamic programming approach to the generalized minimum Manhattan network problem
• A catalog of Hanan grid problems
• Embedding rectilinear Steiner trees with length restrictions
• The Rectilinear Steiner Arborescence Problem Is NP-Complete
• Optimal competitiveness for the rectilinear Steiner arborescence problem
• The Steiner tree problem for terminals on the boundary of a rectilinear polygon
• The rectilinear Steiner tree problem with given topology and length restrictions
• Steiner trees with bounded RC-delay

This page was built for publication: The rectilinear Steiner arborescence problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1186802)