ALGORITHMS FOR ROUTING AROUND A RECTANGLE

被引：39
作者：
FRANK, A
NISHIZEKI, T
SAITO, N
SUZUKI, H
TARDOS, E
机构：
[1] CORNELL UNIV, SCH OPERAT RES, ITHACA, NY 14853 USA
[2] EOTVOS LORAND UNIV, DEPT COMP SCI, H-1364 BUDAPEST 5, HUNGARY
[3] TOHOKU UNIV, FAC ENGN, DEPT ELECT COMMUN, SENDAI, MIYAGI 980, JAPAN
来源：
DISCRETE APPLIED MATHEMATICS | 1992年 / 40卷 / 03期
关键词：
D O I：
10.1016/0166-218X(92)90007-W
中图分类号：
O29 [应用数学];
学科分类号：
070104 ;
摘要：
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. Our simple linear time algorithm is based on a theorem of Okamura and Seymour and on a data structure developed by Suzuki, Ishiguro and Nishizeki.
引用
收藏
页码：363 / 378
页数：16
相关论文
共 9 条
1