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)+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).
Details
Title
Finding all the perfect matchings in bipartite graphs
Author(s)
Fukuda, K. ; Matsui, T.
Published in
Applied Mathematics Letters
Volume
7
Issue
1
Pages
15-18
Date
1994
Note
PRO 94.13
Laboratories
ROSO
Record Appears in
Scientific production and competences > SB - School of Basic Sciences > SB Archives > ROSO - Chair of Operations Research SO
Scientific production and competences > SB - School of Basic Sciences > Mathematics
Peer-reviewed publications
Work produced at EPFL
Journal Articles
Published
Scientific production and competences > SB - School of Basic Sciences > Mathematics
Peer-reviewed publications
Work produced at EPFL
Journal Articles
Published
Record creation date
2006-02-13