四正则图的纵横嵌入优化并行算法

摘要

纵横嵌入术已为超大规模集成电路(VLSI)的平面设计提供了较完备的理论体系,在EREW PRAM(Exclusive-Rread and Exclusive-Write Parallel Random Access Machine)并行计算模型上,使用O((m+n)/ logn)个处理器,时间复杂度为O(logn),对四正则图的纵横嵌入图优化,使图中边的总折数达到最少且所占面积最小.