Finding All the Perfect Matchings in Bipartite Graphs. Fukuda, K. & Matsui, T. Applied Mathematics Letters, 7(1):15--18, January, 1994.
Finding All the Perfect Matchings in Bipartite Graphs [link]Paper  doi  abstract   bibtex   
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)+n2.5) computational effort and O(nm) memory 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).
@article{ Fukuda1994,
  abstract = {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)+n2.5) computational effort and O(nm) memory 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).},
  author = {Fukuda, K. and Matsui, T.},
  doi = {10.1016/0893-9659(94)90045-0},
  file = {:Users/KunihiroWASA/Dropbox/paper/1994/Fukuda, Matsui, Finding All the Perfect Matchings in Bipartite Graphs, 1994.pdf:pdf},
  issn = {08939659},
  journal = {Applied Mathematics Letters},
  keywords = {Bipartite graph,Enumeration.,Matching},
  month = {January},
  number = {1},
  pages = {15--18},
  title = {{Finding All the Perfect Matchings in Bipartite Graphs}},
  url = {http://www.sciencedirect.com/science/article/pii/0893965994900450 http://linkinghub.elsevier.com/retrieve/pii/0893965994900450},
  volume = {7},
  year = {1994}
}

Downloads: 0