A family of bipartite cardinality matching problems solvable in O ( n 2 ) time
Jens Clausen, Jakob Krarup · Nordic journal of computing · 1995
For a given, unweighted bipartite graph G with 2n non-isolated vertices, we consider the so-called Bipartite Cardinality Matching Problem (BCMP) for which the time complexity of the fastest exact algorithm available is O(n5/2). We devise a greedy algorithm which either finds a perfect matching in O(n2) time or identifies cycle of length 4 in the complement G of G