Open AccessA Fast Algorithm for Enumerating Bipartite Perfect Matchings
Author(s) -
Takeaki Uno
Publication year - 2001
Publication title -
lecture notes in computer science
Language(s) - English
Resource type - Book series
SCImago Journal Rank - 0.249
H-Index - 400
eISSN - 1611-3349
pISSN - 0302-9743
DOI - 10.1007/3-540-45678-3_32
Subject(s) - bipartite graph , computer science , matching (statistics) , algorithm , blossom algorithm , 3 dimensional matching , graph , combinatorics , theoretical computer science , discrete mathematics , mathematics , statistics
In this paper, we propose an algorithm for enumerating all the perfect matchings included in a given bipartite graph G = (V,E). The algorithm is improved by the approach which we proposed at ISAAC98. Our algorithm takes O(log |V|) time per perfect matching while the current fastest algorithm takes O(|V|) time per perfect matching.
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom