Algorithms for VLSI Design Automation

Programming Project (for one or two persons): Single-Layer 1D Compaction

Summary: This project aims at implementing a simplified version of 1D compaction that still contains most of the essential issues of the problem: respecting design rules and preservation of connectivity for a single layout layer. For this purpose, a constraint graph needs to be built. The solution of the longest-path problem in this graph gives the optimally compacted layout. Starting compaction with a minimal-size (irredundant) constraint graph reduces the time needed for the longest-path algorithms.

Detailed Description

Last update on: Mon May 28 18:11:20 CEST 2007 by Sabih Gerez.