Algorithmic Aspects of One-Dimensional Layout Compaction
- 1 September 1987
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
- Vol. 6 (5) , 863-878
- https://doi.org/10.1109/tcad.1987.1270329
Abstract
We present a theory of one-dimensional layout compaction that is based on the graph theoretic approach used in such compacters as reported in [5], [7], [11], and [26]. Compaction here consists of two steps. In the first stage, a directed graph is extracted from the layout. In the second stage, compaction is performed by solving a single-source shortest path problem on this graph. The paper presents new efficient algorithms and/or heuristics for the first stage of the compaction process. A compacter based on the framework presented here that incorporates the algorithms described is a powerful tool that can easily be tailored to specific applications. It allows a tradeoff between the space and runtime performance of the compacter and the quality of the compaction.Keywords
This publication has 16 references indexed in Scilit:
- On the solution of inequality systems relevant to IC-layoutJournal of Algorithms, 1984
- An algorithm for optimal two-dimensional compaction of VLSI layoutsIntegration, 1983
- An Algorithm to Compact a VLSI Symbolic Layout with Mixed ConstraintsIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1983
- The complexity of compacting hierarchically specified layouts of integrated circuitsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1982
- Layout aid for the design of VLSI circuitsComputer-Aided Design, 1981
- MULGA-An Interactive Symbolic Layout System for the Design of Integrated CircuitsBell System Technical Journal, 1981
- The Transitive Reduction of a Directed GraphSIAM Journal on Computing, 1972
- IC mask layout with a single conductor layerPublished by Association for Computing Machinery (ACM) ,1970
- GRAPH THEORYPublished by Defense Technical Information Center (DTIC) ,1969
- On a routing problemQuarterly of Applied Mathematics, 1958