Given an unweighted bipartite graph which has a perfect matching, is there an algorithm for finding a perfect matching in the graph that is faster than the best known algorithm for finding a maximum cardinality matching (MCM)? For example, is there some way to take advantage of the fact that the graph is known to have some perfect matching to help find one faster?If yes, could you please help to point out some references? If it is impossible, could you briefly explain the reason? Comments and suggestions are also welcomed.
Find perfect matching faster than MCM, in graph that has perfect matching?
algorithms;graph theory;algorithm analysis;bipartite matching;matching