一种求偶图的所有完备匹配算法
AN ALGORITHM FOR FINDING ALL PERFECT MATCHINGS IN A BIPARTITE GRAPH
-
摘要: 求给定偶图的所有完备匹配问题在LSI/VLSI的布图设计方面有着重要的应用。本文提出了一种求解这一问题的算法。(1)提出了许配树的概念并讨论了其性质;(2)证明了任意一棵许配树T(xi)对应于给定偶图的所有完备匹配的定理;(3)给出了求给定偶图的所有完备匹配的算法。本算法已在BST 386 CAD工作站上用C语言实现。运行结果证明了算法的正确性。算法已作为正在研充的VLSI积木块布图设计系统中的一个模块。Abstract: 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 laave been obtain-ed. The algorithm has also been employed as a program block in our VLSI building block layout system which has been developing.
-
J. Edmonds, Can. J. Math., 17(1965)3, 449-467.[2]i陈立东,张良震,庄文君,电子学报,16(1988)l,53-58.[3]M.N.S. Swamy et al.,Graphs, Networks, and Algorithms, John Wiley Sons, Inc. New York,(1981).[4]N. Deo, Graph Theory with Applications to Engineering and Computer Science, Prentice-Hall, Inc., (1974), pp. 117-181.[5]M. Fukui et al., IEEE Trans. on CAD, CAD-6(1987)3, 383-391. -
计量
- 文章访问数: 2279
- HTML全文浏览量: 101
- PDF下载量: 457
- 被引次数: 0
下载:
