One-dimensional logic gate assignment and interval graphs

T. Ohtsuki, H. Mori, E.S. Kuh et al. · IEEE Transactions on Circuits and Systems · 1979

This paper gives a graph-theoretic approach to the design of one-dimensional logic gate arrays using MOS orI^{2}Lunits. The incidence relation between gates and nets is represented by a graphH=(V,E), and a possible layout of gates and nets is characterized by an interval graph\hat{H} = (V, E \cup F), whereFis called an augmentation. It is shown that the number of tracks required for between-gate wiring is equal to the clique number (chromatic number) ofH, and hence the optimum placement problem is converted to that of minimum clique number augmentation. This turns out to be anNP-complete problem. Instead a polynomial-time algorithm for finding a minimal augmentation is presented, where an augmentation is minimal if no proper subset of it is an augmentation. An algorithm for gate sequencing with respect to a given augmentation is also presented.

Cited by 109 works. doi:10.1109/tcs.1979.1084695

Authors

References