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

Bradley S. Carlson, C. Y. Roger Chen, Dikran S. Meliksetian

Research output: Chapter in Book/Report/Conference proceedingConference contribution

2 Scopus citations

Abstract

A linear time algorithm is presented which identifies the dual Eulerian property in a plane undirected multigraph. 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.

Original languageEnglish (US)
Title of host publication1992 IEEE International Symposium on Circuits and Systems, ISCAS 1992
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages2248-2251
Number of pages4
ISBN (Electronic)0780305930
DOIs
StatePublished - Jan 1 1992
Event1992 IEEE International Symposium on Circuits and Systems, ISCAS 1992 - San Diego, United States
Duration: May 10 1992May 13 1992

Publication series

NameProceedings - IEEE International Symposium on Circuits and Systems
Volume5
ISSN (Print)0271-4310

Conference

Conference1992 IEEE International Symposium on Circuits and Systems, ISCAS 1992
CountryUnited States
CitySan Diego
Period5/10/925/13/92

ASJC Scopus subject areas

  • Electrical and Electronic Engineering

Fingerprint Dive into the research topics of 'An efficient algorithm for the identification of dual eulerian graphs and its application to cell layout'. Together they form a unique fingerprint.

  • Cite this

    Carlson, B. S., Roger Chen, C. Y., & Meliksetian, D. S. (1992). An efficient algorithm for the identification of dual eulerian graphs and its application to cell layout. In 1992 IEEE International Symposium on Circuits and Systems, ISCAS 1992 (pp. 2248-2251). [230512] (Proceedings - IEEE International Symposium on Circuits and Systems; Vol. 5). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/ISCAS.1992.230512