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

Ishwar Baidari, Vijaykumar Gurani

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.


Full Text: PDF

How to Cite this Article:

Ishwar Baidari, Vijaykumar Gurani, A simple algorithm to find maximum matching for complete graph and complete bipartite graph: using incidence matrix approach, Journal of Mathematical and Computational Science, Vol 6, No 2 (2016), 272-280

Copyright © 2016 Ishwar Baidari, Vijaykumar Gurani. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

J. Math. Comput. Sci.

ISSN: 1927-5307

Editorial Office: jmcs@scik.org

 

Copyright ©2019 JMCS