Finding All the Perfect Matchings in Bipartite Graphs. Fukuda, K. & Matsui, T. Applied Mathematics Letters, 7(1):15--18, January, 1994.
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
{"_id":"gFo8RPDmjPYfEkjY3","authorIDs":[],"author_short":["Fukuda, K.","Matsui, T."],"bibbaseid":"fukuda-matsui-findingalltheperfectmatchingsinbipartitegraphs-1994","bibdata":{"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.","Matsui, T."],"author_short":["Fukuda, K.","Matsui, T."],"bibtex":"@article{ Fukuda1994,\n 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).},\n author = {Fukuda, K. and Matsui, T.},\n doi = {10.1016/0893-9659(94)90045-0},\n file = {:Users/KunihiroWASA/Dropbox/paper/1994/Fukuda, Matsui, Finding All the Perfect Matchings in Bipartite Graphs, 1994.pdf:pdf},\n issn = {08939659},\n journal = {Applied Mathematics Letters},\n keywords = {Bipartite graph,Enumeration.,Matching},\n month = {January},\n number = {1},\n pages = {15--18},\n title = {{Finding All the Perfect Matchings in Bipartite Graphs}},\n url = {http://www.sciencedirect.com/science/article/pii/0893965994900450 http://linkinghub.elsevier.com/retrieve/pii/0893965994900450},\n volume = {7},\n year = {1994}\n}","bibtype":"article","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","id":"Fukuda1994","issn":"08939659","journal":"Applied Mathematics Letters","key":"Fukuda1994","keywords":"Bipartite graph,Enumeration.,Matching","month":"January","number":"1","pages":"15--18","title":"Finding All the Perfect Matchings in Bipartite Graphs","type":"article","url":"http://www.sciencedirect.com/science/article/pii/0893965994900450 http://linkinghub.elsevier.com/retrieve/pii/0893965994900450","volume":"7","year":"1994","bibbaseid":"fukuda-matsui-findingalltheperfectmatchingsinbipartitegraphs-1994","role":"author","urls":{"Paper":"http://www.sciencedirect.com/science/article/pii/0893965994900450 http://linkinghub.elsevier.com/retrieve/pii/0893965994900450"},"keyword":["Bipartite graph","Enumeration.","Matching"],"downloads":0,"html":""},"bibtype":"article","biburl":"http://www-ikn.ist.hokudai.ac.jp/~wasa/enum.bib","creationDate":"2015-04-23T04:51:44.865Z","downloads":0,"keywords":["bipartite graph","enumeration.","matching"],"search_terms":["finding","perfect","matchings","bipartite","graphs","fukuda","matsui"],"title":"Finding All the Perfect Matchings in Bipartite Graphs","year":1994,"dataSources":["YRMeqhMHoNu9HzJoC"]}