Browse Prior Art Database

New Method for Rectilinear Steiner Trees

IP.com Disclosure Number: IPCOM000036191D
Original Publication Date: 1989-Sep-01
Included in the Prior Art Database: 2005-Jan-28

Publishing Venue

IBM

Related People

Authors:
Ho, JM Vijayan, G Wong, CK [+details]

Abstract

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.