ISSN:
1432-0541
Keywords:
Key words. VLSI layout, Compaction, Graph constraints, Constraint graphs, Constraint reduction, Transitive reduction, Difference constraints.
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
,
Mathematics
Notes:
Abstract. The compaction problem in VLSI layout can be formulated as a linear program. To reduce the execution time and memory usage in compaction, it is important to reduce the size of the linear program. Since most constraints in compaction are derived directly or indirectly from physical separation and electrical connectivity requirements which can be expressed in the form of graph constraints, we study the graph constraint reduction problem. That is the problem of producing, for a given system of graph constraints, an equivalent system with the fewest graph constraints. After observing that the problem as previously formulated is NP-hard and overrestrictive in that the maximum possible reduction is not always attainable, we propose a new formulation in which the maximum possible reduction is guaranteed. We further present a polynomial-time algorithm for the new formulation.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/PL00009173
Permalink
