摘要
求给定偶图的所有完备匹配问题在LSI/VLSI的布图设计方面有着重要的应用。本文提出了一种求解这一问题的算法。(1)提出了许配树的概念并讨论了其性质;(2)证明了任意一棵许配树T(xi)对应于给定偶图的所有完备匹配的定理;(3)给出了求给定偶图的所有完备匹配的算法。本算法已在BST 386 CAD工作站上用C语言实现。运行结果证明了算法的正确性。算法已作为正在研充的VLSI积木块布图设计系统中的一个模块。
Finding all perfect matchings in a given bipartite graph has importantapplications to the global routing and channel ordering for VLSI building block layout. An algorithm for finding all perfect matchings in a given bipartite graph G(X,Y, E) is presented. First, the definition of marriage tree T(xi) is proposed and some properties of T(XI) are discussed. Second, it is proved that anyone of marriage trees, T(xi), resulted from G(X,Y,E) corresponds to all perfect matchings in G(X,Y,E). Finally, discription of the algorithm is given. The algorithm has been implemented in C language and good results have been obtained. The algorithm has also been employed as a program block in our VLSI building block layout system which has been developing.
基金
国家自然科学基金
关键词
图论
应用
偶图
完备匹配
许配树
Graph theory and its applications
Bipartite graph
Perfect matching
Marriage tree
