Augmenting Matching Algorithm on the Bipartite Graphs

Abstract

Discrete or Decision Mathematics is a useful subject for making the undesirable or impossible decisions especially for the assignment problems. These problems can be expressed in the graphs because graphs are used to solve problems in many fields and applications. Some applications are scheduling, finding the shortest paths and matching the elements of two different sets which are called the assignment problems. Although there are many kinds of graphs, the bipartite graphs provide the most useful way to represent the matching problems. This paper represents how the matching problems are implemented in the bipartite graphs and (0, 1) matrices. It also shows how the augmenting matching algorithm is applied in these problems to get the complete matching. It also shows that the original or the user chosen matching is already maximal for some cases. In this paper, the personnel assignment problem is used as the typical matching problem.