Given a set N of n terminals in the first quadrant of the Euclidean plane E2, find a minimum length directed tree rooted at the origin o, connecting to all terminals in N, and consisting of only horizontal and vertical arcs oriented from left to right or from bottom to top. This problem is called rectilinear Steiner arborescence problem, which has been proved to be NP-complete recently. In this paper, we present a polynomial time approximation scheme for this problem.
Lu, Bing; Ruan, Lu.
Polynomial Time Approximation Scheme for the Rectilinear Steiner Arborescence Problem.
Retrieved from the University of Minnesota Digital Conservancy,
Content distributed via the University of Minnesota's Digital Conservancy may be subject to additional license and use restrictions applied by the depositor.