A new graph coloring algorithm for constrained via minimization

Author

Noteboom, Ron ; Ali, Hesham H.

Author_Institution

Dept. of Comput. Sci., Nebraska Univ., Omaha, NE, USA

Volume

1

fYear

1994

fDate

3-5 Aug 1994

Firstpage

363

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 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 planar 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 mutilayers

Keywords

VLSI; circuit layout CAD; computational complexity; graph colouring; graph theory; integrated circuit layout; network topology; NP-complete; VLSI chip design; constrained via minimization; graph coloring algorithm; intersect graph model; layer assignment algorithm; mutilayers; nonplanar graphs; planar graphs; polynomial solution; pseudo two coloring technique; two coloring heuristic; Chip scale packaging; Circuit synthesis; Computer science; Fabrication; Metalworking machines; Minimization methods; Polynomials; Routing; Very large scale integration; Wire;

fLanguage

English

Publisher

ieee

Conference_Titel

Circuits and Systems, 1994., Proceedings of the 37th Midwest Symposium on

Conference_Location

Lafayette, LA

Print_ISBN

0-7803-2428-5

Type

conf

DOI

10.1109/MWSCAS.1994.519257

Filename

519257