The rectilinear Steiner arborescence problem (Q1186802): Difference between revisions

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.