Abstract
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.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
K. Fukuda and T. Matsui, “Finding All the Perfect Matchings in Bipartite Graphs,” Appl. Math. Lett. 7, No. 1, 15–18 (1994).
J. E. Hopcroft and R. M. Karp, “An n 5/2 Algorithm for Maximum Matching in Bipartite Graphs,” SIAM J. Comp. 2, 225–231 (1973).
T. Uno, “Algorithms for Enumerating All Perfect, Maximum and Maximal Matchings in Bipartite Graphs,” Lecture Note in Computer Science 1350, Springer-Verlag, Algorithms and Computation, 92–101 (1997).
T. Uno, “A New Approach for Speeding Up Enumeration Algorithms,” Lecture Note in Computer Science 1533, Springer-Verlag, Algorithms and Computation, 287–296 (1998).
T. Uno, “A New Approach for Speeding Up Enumeration Algorithms and Its Application for Matroid Bases,” Lecture Note in Computer Science 1627, Springer-Verlag, Computing and Combinatorics (Proceeding of COCOON99), 349–359, (1999)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2001 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Uno, T. (2001). A Fast Algorithm for Enumerating Bipartite Perfect Matchings. In: Eades, P., Takaoka, T. (eds) Algorithms and Computation. ISAAC 2001. Lecture Notes in Computer Science, vol 2223. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-45678-3_32
Download citation
DOI: https://doi.org/10.1007/3-540-45678-3_32
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-42985-2
Online ISBN: 978-3-540-45678-0
eBook Packages: Springer Book Archive