Finding the Maximum Matching in a Bipartite Graph
B. M. Monjurul Alom, Md. Saiful Islam · 2010
A matching M of the graph G is an edge set such that no two edges of M share their endpoints. For a bipartite graph G = (V, E) maximum matching are matching whose cardinalities are maximum among all matchings. Existing enumerating algorithm of maximum matching has time complexity is O(|V |) per matching. FordFulkerson method finds the maximum matching on a bipartite graph with O(VE) time. In this paper, an algorithm to find the maximum matching on a bipartite graph with O(E) time is presented which is less than the time complexity of the existing algorithms.