Loading...
research article
Finding all the perfect matchings in bipartite graphs
This paper describes an algorithm for finding all the perfect matchings in a bipartite graph. By using the binary partitioning method, our algorithm requires O(c(n+m)+n^2.5) computational effort and O(nm) memmory storage, (where n denotes the number of vertices, m denotes the number of edges, and c denotes the number of perfect matchings in the given bipartite graph).
Type
research article
Author(s)
Date Issued
1994
Published in
Volume
7
Issue
1
Start page
15
End page
18
Note
PRO 94.13
Peer reviewed
REVIEWED
Written at
EPFL
EPFL units
Available on Infoscience
February 13, 2006
Use this identifier to reference this record