Title :
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
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;
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
DOI :
10.1109/ISCAS.1992.230512
