IEEE Transactions on Circuits and Systems · 1979 · 107 citations · 10 references
EngineeringComputer EngineeringElectrical EngineeringCircuit TheoryMicroelectronicsVlsi DesignBoolean OperationsDigital Logic DesignGraph TheoryLogic SynthesisVery-large-scale Integration LayoutCircuit Graph TheoryGate-level DesignGraph-theoretic Circuit FormulationGraph-theoretic Layout AnalysisLogic Gate DesignLogic Gate ImplementationLogic Gate Networks
This paper gives a graph-theoretic approach to the design of one-dimensional logic gate arrays using MOS or <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">I^{2}L</tex> units. The incidence relation between gates and nets is represented by a graph <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">H=(V,E)</tex> , and a possible layout of gates and nets is characterized by an interval graph <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">\hat{H} = (V, E \cup F)</tex> , where <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">F</tex> is called an augmentation. It is shown that the number of tracks required for between-gate wiring is equal to the clique number (chromatic number) of <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">H</tex> , and hence the optimum placement problem is converted to that of minimum clique number augmentation. This turns out to be an <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">NP</tex> -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.
10
Incidence matrices and interval graphs
D. R. Fulkerson, Oliver Gross · Pacific Journal of Mathematics · 1965 · 1.3K citations · Full text
Dominic Welsh · Bulletin of the London Mathematical Society · 1974 · 1.1K citations