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
- Graphs and Hypergraphs
- GRAPHS AND HYPERGRAPHS
- Incidence matrices and interval graphs
- Algorithmic Aspects of Vertex Elimination on Graphs
- Wire routing by optimizing channel assignment within large apertures
- Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
- Large Scale Integration of MOS Complex Logic: A Layout Method
- Computer-Aided Preliminary Layout Design of Customized MOS Arrays
- All approach to the two-dimensional placement problem in circuit layout
- A heuristic procedure for ordering MOS arrays