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: | Frank Andrs, Tardos va, Nishizeki Takao, Suzuki Hitoshi, Saito Nobuji |
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(