| Paper title: |
Algorithm Analytic To Find Maximum Matching In Bipartite Graph |
| DOI: | https://doi.org/10.4316/JACSM.202001004 |
| Published in: | Issue 1, (Vol. 14) / 2020 |
| Publishing date: | 2020-04-25 |
| Pages: | 25-29 |
| Author(s): | VALENCIANO Alvin, ISTIONO Wirawan |
| Abstract. | Matching is a set of edges in a graph which each of the edge does not share a common vertex. Maximum Matching in a graph is number of maximum matching which a graph can have. Graph that will be used is guaranteed to be a bipartite graph that each of the vertices can be divided into two independent sets and edges in that graph always connect two vertices from different set. Topic in this journal is to find maximum matching in a graph. There are several approaches and optimizations to be done to achieve intended optimal solution. One of those optimization is vertices and edges compression so the algorithm can safely ignore duplicate vertices and edges in the graph. Purpose of this journal is to find accuracy and time complexity of all algorithm used to find maximum matching. |
| Keywords: | Maximum Matching, Bipartite Graph; Depth-First Search, Maximum Flow |
| References: | 1. Yannick Rochat. Jorge Pena, "Bipartite Graphs as Models of Population Structures in Evolutionary Multiplayer Games," journal Plos one, p. 13, 2012. 2. B. M. Monjurul Alom, Someresh Das and Md. Saiful Islam, "Finding the Maximum Matching in a Bipartite Graph," vol. 1, no. 1, p. 33, June 2010. 3. Harmanjit Singh. R. Sharma, "Role of Adjacency Matrix & Adjacency List in Graph Theory," Graph Representation, vol. 3, p. 179, 2012. ` 4. T. Uno, "Algorithms for Enumerating All Perfect, Maximum and Maximal Matchings in Bipartite Graphs," Maximum Bipartite Matching Problem. 5. T. M. K. Fukuda, "Finding All Minimum Cost Perfect Matchings in Bipartite Graphs," Minimum Cost Perfect Matching. 6. Thomas H. Cormen et al. "Introduction to Algorithms," September 2001. 7. HK Hwang, "Presorting algorithms: An average-case point of view," Presorting, pp. 29-31, 2000. 8. H. N. I. K. M. A. C. M. M. R. Irfan Ali, "Performance Comparison between Merge and Quick Sort Algorithms in Data," International Journal of Advanced Computer Science and Applications, p. 5, 2018. 9. Irfan Ali, Imran Khan Keerio et.al. "An Algorithmic Study of the Maximum Flow," Comparative Statistical Analysis, vol. 8, no. 1, pp. 136-162, 2000. 10. Feiyang Chen, Nan Chen , Hanyang Mao, Hanlin Hu "The Application of Bipartite Matching in Assignment Problem," Matching in Bipartite Graph, p. 1, 2018. 11. D. Casperson, "Towards a Better Presentation of Dynamic Programming," May 2014. 12. Penny Haxell, Lothar Narins, "A Stability Theorem for Matchings in Tripartite 3-Graphs," pp. 1-19, 2018. |
| Back to the journal content | |
