The rectilinear Steiner arborescence problem

DOI10.1007/BF01758762zbMATH Open0773.05041OpenAlexW1988808425MaRDI QIDQ1186802FDOQ1186802

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

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

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)

Cites Work

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

Cited In (26)

• 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
• Logic Programming
• Two variations of the minimum Steiner problem
• 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
• Title not available (Why is that?)
• 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
• 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)