An efficient algorithm for the identification of dual Eulerian graphs and its application to cell layout

Author

Carlson, Bradley S. ; Chan, C.Y.R. ; Meliksetian, Dikran S.

Author_Institution

Dept. of Electr. Eng., State Univ. of New York, Stony Brook, NY, USA

Volume

5

fYear

1992

fDate

10-13 May 1992

Firstpage

2248

Abstract

A linear time algorithm which identifies the dual Eulerian property in a plane undirected multigraph is presented. This graph property is important in the generation of layouts of CMOS circuits for VLSI design. A linear time heuristic algorithm is presented for the more general dual path cover problem which is known to be NP-hard. The algorithm operates on non-series/parallel graphs in addition to series/parallel graphs, determines very good solutions and its time complexity is linear with respect to the number of edges in the graph. The algorithm has produced optimal results for more than 80% of over 300 test cases

Keywords

CMOS integrated circuits; VLSI; circuit layout CAD; graph theory; identification; CMOS circuits; NP-hard; VLSI design; cell layout; dual Eulerian graphs; dual path cover problem; identification; linear time algorithm; linear time heuristic algorithm; plane undirected multigraph; Circuits; Heuristic algorithms; Very large scale integration;

fLanguage

English

Publisher

ieee

Conference_Titel

Circuits and Systems, 1992. ISCAS '92. Proceedings., 1992 IEEE International Symposium on

Conference_Location

San Diego, CA

Print_ISBN

0-7803-0593-0

Type

conf

DOI

10.1109/ISCAS.1992.230512

Filename

230512