论文部分内容阅读
求给定偶图的所有完备匹配问题在LSI/VLSI的布图设计方面有着重要的应用。本文提出了一种求解这一问题的算法。(1)提出了许配树的概念并讨论了其性质;(2)证明了任意一棵许配树T(xi)对应于给定偶图的所有完备匹配的定理;(3)给出了求给定偶图的所有完备匹配的算法。本算法已在BST 386 CAD工作站上用C语言实现。运行结果证明了算法的正确性。算法已作为正在研充的VLSI积木块布图设计系统中的一个模块。