J. Nievergelt, J. Pradels, et al.
Information Processing Letters
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
J. Nievergelt, J. Pradels, et al.
Information Processing Letters
C.K. Wong, P.C. Yue
Information Sciences
G.Y. Yan, J.F. Pan, et al.
Graphs and Combinatorics
C.K. Wong, M.C. Easton
Journal of the ACM