New approximations for the rectilinear steiner arborescence problem
Sarnath Ramnath · IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems · 2003
A new approach for approximating the minimum rectilinear Steiner arborescence is presented. The approach yields a simple two-approximation algorithm that runs in O(nlogn) time. Unlike earlier approaches, this can be naturally extended to deal with situations where we have isothetic rectilinear obstacles. This gives us the first O(nlogn) two-approximation algorithm for the rectilinear Steiner arborescence problem in the presence of obstacles.