A simple algorithm to find maximum matching for complete graph and complete bipartite graph: using incidence matrix approach

Abstract

A simple graph G(V,E) has vertex set V and edge set E then matching means a subset S of the edge set E such that no two edges of S are adjacent in E. If S is matching, the two end points of each edge of S are said to be matched under S, and each vertex incident with an edge of S is said to be covered by S. The matching S with maximum number of edges is called maximum matching. In this paper we present a polynomial time algorithm to find maximum matching for complete graph and complete bipartite graph using incidence matrix approach.