Polynomial time manhattan routing without doglegs - a generalization of gallai's algorithm
Abstract
Gallai's classical result on interval packing can be applied in VLSI routing to find, in linear time, a minimum/width dogleg/free routing in the Manhattan model, provided that all the terminals are on one side of a rectangular [1]. Should the terminals appear on two opposite sides of a rectangular, the corresponding "channel routing problem" is NP/complete [2,3]. We generalize Gallai's result for the case if the terminals appear on two adjacent sides of the rectangular.Downloads
Download data is not yet available.
Published
2012-03-01
How to Cite
Boros, E., Recski, A., Szkaliczki, T., & Wettl, F. (2012). Polynomial time manhattan routing without doglegs - a generalization of gallai’s algorithm. Computing and Informatics, 18(4), 403–413. Retrieved from http://147.213.75.17/ojs/index.php/cai/article/view/593
Issue
Section
Articles