Augmenting Matching Algorithm on the Bipartite Graphs
Wai Oo Paing, Khin Phyo Thant · 2010
Discrete or Decision Mathematics is auseful subject for making the undesirable orimpossible decisions especially for the assignmentproblems. These problems can be expressed in thegraphs because graphs are used to solve problemsin many fields and applications. Some applicationsare scheduling, finding the shortest paths andmatching the elements of two different sets whichare called the assignment problems. Although thereare many kinds of graphs, the bipartite graphsprovide the most useful way to represent thematching problems. This paper represents how thematching problems are implemented in the bipartitegraphs and (0, 1) matrices. It also shows how theaugmenting matching algorithm is applied in theseproblems to get the complete matching. It alsoshows that the original or the user chosen matchingis already maximal for some cases. In this paper, thepersonnel assignment problem is used as the typicalmatching problem.