Etd

Dual-Eulerian Graphs with Applications to VLSI Design

Public

Contenu téléchargeable

open in viewer

A Dual-Eulerian graph is a plane multigraph G that contains an edge list which is simultaneously an Euler tour in G and an Euler tour in the dual of G. Dual-Eulerian tours play an important role in optimizing CMOS layouts of Boolean functions. When circuits are represented by undirected multigraphs the layout area of the circuit can be optimized through finding the minimum number of disjoint dual trails that cover the graph. This paper presents an implementation of a polynomial time algorithm for determining whether or not a plane multigraph is Dual-Eulerian and for finding the Dual-Eulerian trail if it exists.

Creator
Contributeurs
Degree
Unit
Publisher
Language
  • English
Identifier
  • etd-0430103-155731
Mot-clé
Advisor
Defense date
Year
  • 2003
Date created
  • 2003-04-30
Resource type
Rights statement

Relations

Dans Collection:

Contenu

Articles

Permanent link to this page: https://digital.wpi.edu/show/z316q165r