The rectilinear Steiner arborescence problem
type: Item
instance of: scholarly article
title: The rectilinear Steiner arborescence problem
zbMATH Open document ID: 0773.05041
DOI: 10.1007/BF01758762
author: Sailesh K. Rao
author: P. Sadayappan
author: Frank K. Hwang
author: Peter W. Shor
published in: Algorithmica
publication date: 1992-06-28T00:00:00Z
review text: The Rectilinear Steiner Arborescence (RSA) problem is: Given a set \(N\) of \(n\) nodes lying in the first quadrant of \(E^ 2\), find the shortest directed tree rooted at the origin, containing all nodes in \(N\), and composed solely of horizontal and vertical arcs oriented only from left to right or from bottom to top. The authors investigate some fundamental properties of the RSA problem and give an \(O(n^ 3)\)-algorithm if an RSA for \(N\) has the property that no point has a path to any other point. In the comparision aborescences versus trees it holds that the Rectilinear Minimum Spanning Arborescence (RMSA) can be constructed fast, but is not a good heuristic arborescence, because the maximal ratio equals \(\Omega(n/\log n)\). The maximal value for length of an RSMA divided by the length of a Rectilinear Steiner Minimal Tree equals \(\Theta(\log n)\). A heuristic is proposed which runs in \(O(n\log n)\)-time and produces an RSA whose length has an upper bound of twice that of the minimum length RSA. It is shown that a polynomial-time algorithm that was earlier reported in the literature for this problem is incorrect.
Mathematics Subject Classification ID: 05C05
Mathematics Subject Classification ID: 05C20
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 37173
zbMATH Keywords: rectilinear Steiner arborescence
zbMATH Keywords: Steiner trees
zbMATH Keywords: rectilinear distance
zbMATH Keywords: directed graphs
zbMATH Keywords: algorithm
reviewed by: Dietmar Cieslik
MaRDI profile type: Publication
cites work: On Steiner trees for bounded point sets
cites work: The shortest path and the shortest road through n points
cites work: The Rectilinear Steiner Tree Problem is $NP$-Complete
cites work: On Steiner’s Problem with Rectilinear Distance
cites work: On Steiner Minimal Trees with Rectilinear Distance
cites work: An O ( n log n ) Algorithm for Rectilinear Minimal Spanning Trees
cites work: Cost-minimal trees in directed acyclic graphs
cites work: Finding optimum branchings
cites work: Subclass of the Steiner problems on a plane with rectilinear metric
full work available at URL: https://doi.org/10.1007/bf01758762
OpenAlex ID: W1988808425
description: scientific article; zbMATH DE number 37173