AbstractFor 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 \bar{G} of G.
Categories and Subject Descriptors: G.1.6 [Numerical Analysis]: Optimization; G.2.2 [Discrete Mathematics]: Graph Theory
Additional Key Words and Phrases: bipartite cardinality matching, greedy algorithm