一種求偶圖的所有完備匹配算法
AN ALGORITHM FOR FINDING ALL PERFECT MATCHINGS IN A BIPARTITE GRAPH
-
摘要: 求給定偶圖的所有完備匹配問題在LSI/VLSI的布圖設計方面有著重要的應用。本文提出了一種求解這一問題的算法。(1)提出了許配樹的概念并討論了其性質;(2)證明了任意一棵許配樹T(xi)對應于給定偶圖的所有完備匹配的定理;(3)給出了求給定偶圖的所有完備匹配的算法。本算法已在BST 386 CAD工作站上用C語言實現。運行結果證明了算法的正確性。算法已作為正在研充的VLSI積木塊布圖設計系統(tǒng)中的一個模塊。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. -
計量
- 文章訪問數: 2293
- HTML全文瀏覽量: 105
- PDF下載量: 457
- 被引次數: 0
下載:
