Dense layouts for series-parallel circuits
- 10 December 2002
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
Abstract
The authors address the question 'when do three tracks suffice for the gate matrix layout of series-parallel circuits?' and demonstrate that the rather surprising answer appears to be 'almost always.' This is in contrast to the fact that an unbounded number of tracks may be required to layout contrived instances in the worst case. Their approach stems from the novel nonconstructive finite-basis characterization of graphs with k-track layouts for any fixed k.Keywords
This publication has 7 references indexed in Scilit:
- Fast search algorithms for layout permutation problemsIntegration, 1991
- Optimal gate-matrix layout of CMOS functional cellsIntegration, 1990
- Nonconstructive tools for proving polynomial-time decidabilityJournal of the ACM, 1988
- Exact and Approximate Solutions for the Gate Matrix Layout ProblemIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1987
- Graph minors. I. Excluding a forestJournal of Combinatorial Theory, Series B, 1983
- Optimal Layout of CMOS Functional ArraysIEEE Transactions on Computers, 1981
- Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithmsJournal of Computer and System Sciences, 1976