1992, 14(3): 281-285.
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.