K.M. Chung, C.K. Wong
IEEE TC
In this paper, we consider problems of finding assorted rectilinear paths among rectilinear obstacles in two-layer interconnection model according to the number of bends and the 1-layer distance (y-distance). Using a horizontal wavefront approach, optimal θ(eloge) 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 O(e log e) time using O(e log e) space. © 1994 IEEE
K.M. Chung, C.K. Wong
IEEE TC
Ingemar Ingemarsson, C.K. Wong
Information Processing Letters
M. Schlag, Y.Z. Liao, et al.
Integration, the VLSI Journal
Howard H. Chen, C.K. Wong
CICC 1992