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

doi:10.1109/ISCAS.1992.230512

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

Department of Electrical Engineering & Computer Science

Research output: Chapter in Book/Entry/Poem › Conference 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 language	English (US)
Title of host publication	1992 IEEE International Symposium on Circuits and Systems, ISCAS 1992
Publisher	Institute of Electrical and Electronics Engineers Inc.
Pages	2248-2251
Number of pages	4
ISBN (Electronic)	0780305930
DOIs	https://doi.org/10.1109/ISCAS.1992.230512
State	Published - 1992
Event	1992 IEEE International Symposium on Circuits and Systems, ISCAS 1992 - San Diego, United States Duration: May 10 1992 → May 13 1992

Publication series

Name	Proceedings - IEEE International Symposium on Circuits and Systems
Volume	5
ISSN (Print)	0271-4310

Conference

Conference	1992 IEEE International Symposium on Circuits and Systems, ISCAS 1992
Country/Territory	United States
City	San Diego
Period	5/10/92 → 5/13/92

ASJC Scopus subject areas

Electrical and Electronic Engineering

Access to Document

10.1109/ISCAS.1992.230512

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). Article 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

An efficient algorithm for the identification of dual eulerian graphs and its application to cell layout. / Carlson, Bradley S.; Roger Chen, C. Y.; Meliksetian, Dikran S.
1992 IEEE International Symposium on Circuits and Systems, ISCAS 1992. Institute of Electrical and Electronics Engineers Inc., 1992. p. 2248-2251 230512 (Proceedings - IEEE International Symposium on Circuits and Systems; Vol. 5).

Research output: Chapter in Book/Entry/Poem › Conference contribution

Carlson, BS, Roger Chen, CY & Meliksetian, DS 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., 230512, Proceedings - IEEE International Symposium on Circuits and Systems, vol. 5, Institute of Electrical and Electronics Engineers Inc., pp. 2248-2251, 1992 IEEE International Symposium on Circuits and Systems, ISCAS 1992, San Diego, United States, 5/10/92. https://doi.org/10.1109/ISCAS.1992.230512

Carlson BS, Roger Chen CY, Meliksetian DS. 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. Institute of Electrical and Electronics Engineers Inc. 1992. p. 2248-2251. 230512. (Proceedings - IEEE International Symposium on Circuits and Systems). doi: 10.1109/ISCAS.1992.230512

Carlson, Bradley S. ; Roger Chen, C. Y. ; Meliksetian, Dikran S. / An efficient algorithm for the identification of dual eulerian graphs and its application to cell layout. 1992 IEEE International Symposium on Circuits and Systems, ISCAS 1992. Institute of Electrical and Electronics Engineers Inc., 1992. pp. 2248-2251 (Proceedings - IEEE International Symposium on Circuits and Systems).

@inproceedings{27bc718c9b30455a92dc4e1ad8e68aaf,

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

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.",

author = "Carlson, {Bradley S.} and {Roger Chen}, {C. Y.} and Meliksetian, {Dikran S.}",

note = "Publisher Copyright: {\textcopyright} 1992 IEEE.; 1992 IEEE International Symposium on Circuits and Systems, ISCAS 1992 ; Conference date: 10-05-1992 Through 13-05-1992",

year = "1992",

doi = "10.1109/ISCAS.1992.230512",

language = "English (US)",

series = "Proceedings - IEEE International Symposium on Circuits and Systems",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

pages = "2248--2251",

booktitle = "1992 IEEE International Symposium on Circuits and Systems, ISCAS 1992",

}

TY - GEN

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

AU - Carlson, Bradley S.

AU - Roger Chen, C. Y.

AU - Meliksetian, Dikran S.

PY - 1992

Y1 - 1992

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84874253336&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84874253336&partnerID=8YFLogxK

U2 - 10.1109/ISCAS.1992.230512

DO - 10.1109/ISCAS.1992.230512

M3 - Conference contribution

AN - SCOPUS:84874253336

T3 - Proceedings - IEEE International Symposium on Circuits and Systems

SP - 2248

EP - 2251

BT - 1992 IEEE International Symposium on Circuits and Systems, ISCAS 1992

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 1992 IEEE International Symposium on Circuits and Systems, ISCAS 1992

Y2 - 10 May 1992 through 13 May 1992

ER -

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

Abstract

Publication series

Conference

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this