New Method for Rectilinear Steiner Trees
Original Publication Date: 1989-Sep-01
Included in the Prior Art Database: 2005-Jan-28
Disclosed is a new method for obtaining rectilinear Steiner trees. In this method, a rectilinear Minimum Spanning Tree (MST) is globally transformed into a Steiner tree, which is optimum under the operation of flipping the L-shaped edges of the MST. This new approach exploits some ideas that are specific to the rectilinear case and results in a Steiner tree algorithm that is fast, and produces lower cost Steiner trees than those given by previous techniques 3,6,7.