Abstract
This paper proposes a new layer assignment Algorithm for constrained via minimization in VLSI chip design. The new algorithm uses an intersect graph model and applies a pseudo two coloring technique in order to find a near optimal layer assignments in two layers. The pseudo two coloring problem is known to be NP-complete in the general case but a polynomial solution exists for planer graphs. This paper compares the proposed algorithm to optimal results produced in planar and nonplanar graphs as well as to another recent two coloring heuristic in random graphs. The paper also discusses the possibility of extending the algorithm to multilayers.
| Original language | English (US) |
|---|---|
| Title of host publication | Midwest Symposium on Circuits and Systems |
| Editors | Magdy A. Bayoumi, Ken W. Jenkins |
| Place of Publication | Piscataway, NJ, United States |
| Publisher | IEEE |
| Pages | 363-366 |
| Number of pages | 4 |
| Volume | 1 |
| State | Published - 1994 |
| Event | Proceedings of the 37th Midwest Symposium on Circuits and Systems. Part 2 (of 2) - Lafayette, LA, USA Duration: Aug 3 1994 → Aug 5 1994 |
Other
| Other | Proceedings of the 37th Midwest Symposium on Circuits and Systems. Part 2 (of 2) |
|---|---|
| City | Lafayette, LA, USA |
| Period | 8/3/94 → 8/5/94 |
ASJC Scopus subject areas
- Electrical and Electronic Engineering
- Electronic, Optical and Magnetic Materials