Jiang Jianming, Chen Lidong, Zhang Liangzhen. AN ALGORITHM FOR FINDING ALL PERFECT MATCHINGS IN A BIPARTITE GRAPH[J]. Journal of Electronics & Information Technology, 1992, 14(3): 281-285.
Citation:
Jiang Jianming, Chen Lidong, Zhang Liangzhen. AN ALGORITHM FOR FINDING ALL PERFECT MATCHINGS IN A BIPARTITE GRAPH[J]. Journal of Electronics & Information Technology, 1992, 14(3): 281-285.
Jiang Jianming, Chen Lidong, Zhang Liangzhen. AN ALGORITHM FOR FINDING ALL PERFECT MATCHINGS IN A BIPARTITE GRAPH[J]. Journal of Electronics & Information Technology, 1992, 14(3): 281-285.
Citation:
Jiang Jianming, Chen Lidong, Zhang Liangzhen. AN ALGORITHM FOR FINDING ALL PERFECT MATCHINGS IN A BIPARTITE GRAPH[J]. Journal of Electronics & Information Technology, 1992, 14(3): 281-285.
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.
DownLoad: