Algorithms for routing around a rectangle

Algorithms for routing around a rectangle

0.00 Avg rating0 Votes
Article ID: iaor19931496
Country: Netherlands
Volume: 40
Issue: 3
Start Page Number: 363
End Page Number: 378
Publication Date: Dec 1992
Journal: Discrete Applied Mathematics
Authors: , , , ,
Abstract:

Simple efficient algorithms are given for three routing problems around a rectangle. The algorithms find routing in two or three layers for two-terminal nets specified on the sides of a rectangle. All algorithms run in linear time. One of the three routing problems is the minimum area routing previously considered by LaPaugh and Gonzalez and Lee. The algorithms they developed run in time O(n3) and O(n) respectively. The present simple linear time algorithm is based on a theorem of Okamura and Seymour and on a data structure developed by Suzuki, Ishiguro and Nishizeki.

Reviews

Required fields are marked *. Your email address will not be published.