ISSN:
1432-0541
Keywords:
Steiner trees
;
Rectilinear distance
;
Directed graphs
;
Steiner ratio
;
Heuristics
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
,
Mathematics
Notes:
Abstract The Rectilinear Steiner Arborescence (RSA) problem is “Given a setN ofn nodes lying in the first quadrant of E2, find the shortest directed tree rooted at the origin, containing all nodes inN, and composed solely of horizontal and vertical arcs oriented only from left to right or from bottom to top.” In this paper we investigate many fundamental properties of the RSA problem, propose anO(n logn)-time heuristic algorithm giving an RSA whose length has an upper bound of twice that of the minimum length RSA, and show that a polynomial-time algorithm that was earlier reported in the literature for this problem is incorrect.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01758762
Permalink