Title :
On bends and distances of paths among obstacles in two-layer interconnection model
Author :
Lee, D.T. ; Yang, C.D. ; Wong, C.K.
Author_Institution :
Dept. of Electr. Eng. & Comput. Sci., Northwestern Univ., Evanston, IL, USA
fDate :
6/1/1994 12:00:00 AM
Abstract :
We consider problems of finding assorted rectilinear paths among rectilinear obstacles in a two-layer interconnection model according to the number of bends and the 1-layer distance (y-distance). Using a horizontal wave-front approach, optimal θ(e log e) time algorithms are presented to find the shortest path and the minimum-bend path using linear space, and to find the shortest minimum-bend path and the minimum-bend shortest path using O(e log e) space, where e is the number of obstacle edges. By the same approach, we also derive an algorithm for finding a shortest two-layer distance (xy-distance) minimum-bend path in optimal θ(e log e) time using O(e log e) space
Keywords :
computational complexity; computational geometry; minimisation of switching nets; multiprocessor interconnection networks; network synthesis; 2-terminal wire routing; VLSI; bends; computational geometry; distances; horizontal wave-front approach; linear space; minimum-bend path; obstacles; optimal time algorithms; paths; rectilinear paths; shortest path; two-layer interconnection model; Computational geometry; Cost function; Data structures; Helium; Routing; Solid modeling; Time measurement; Very large scale integration; Wire;
Journal_Title :
Computers, IEEE Transactions on
