Abstract
For a bipartite graph G = (V, E), (1) perfect, (2) maximum and (3) maximal matchings are matchings (1) such that all vertices are incident to some matching edges, (2) whose cardinalities are maximum among all matchings, (3) which are contained in no other matching. In this paper, we present three algorithms for enumerating these three types of matchings. Their time complexities are O(|V |) per a matching.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
References
K. Fukuda and T. Matsui, “Finding All the Perfect Matthings in Bipartite Graphs,” Appl. Math. Lett. 7 1 (1994) 15–18
J. E. Hopcroft and R. M. Karp, “An n 5/2 algorithm for maximum matching in bipartite graphs,” SIAM J. on Comp., Vol. 2: 225–231, 1973.
R. E. Tarjan, “Depth-First Search and Linear Graph Algorithm,” SIAM J. Comp. 1, 146–169, 1972.
S.Tsukiyama, M.Ide, H.Ariyoshi and I.Shirakawa, “A New Algorithm for Generating All the Maximum Independent Sets,” SIAM J. Comp.,Vol.6, No.3: 505–517,1977.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1997 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Uno, T. (1997). Algorithms for enumerating all perfect, maximum and maximal matchings in bipartite graphs. In: Leong, H.W., Imai, H., Jain, S. (eds) Algorithms and Computation. ISAAC 1997. Lecture Notes in Computer Science, vol 1350. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-63890-3_11
Download citation
DOI: https://doi.org/10.1007/3-540-63890-3_11
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-63890-2
Online ISBN: 978-3-540-69662-9
eBook Packages: Springer Book Archive