A PARALLEL ALGORITHM FOR MINIMUM DUAL-COVER WITH APPLICATION TO CMOS LAYOUT
YONGGANG HUANG, Majid Sarrafzadeh · Journal of Circuits Systems and Computers · 1991
In a pair of planar graphs (G, G d ), with G d being the dual graph of G, a sequence of distinct edges is a dual-Euler trail if it is a trail both in G and in G d . A set of disjoint dual-Euler trails that simultaneously cover G and G d is called a dual-cover. We present an O( log n) time and O(n) processors algorithm, in PRAM model, based on the graph separator theory, for obtaining a minimum cardinality dual-cover in a pair of series-parallel graphs (G, G d ), where n is the total number of edges. We employ the proposed algorithm to obtain a minimum-area VLSI layout of CMOS functional cells. Our algorithm, when implemented in a serial environment performs better than previous algorithms and produces more compact layouts.