Problem of Maximum Matching in Non-Bipartite Graph Using Edmonds’ Cardinality Matching Algorithm and Its Applicationin the Battle of Britain Case

Muchammad Abrori, Mohammad Imam Jauhari

Abstract


Matching is a part of graph theory that discusses pair. A matching M is called to be maximum if M has the highest number of  elements. A blossom which is encountered in non-bipartite graph can cause failure in process of finding the maximum matching in non-bipartite graph. One of the algorithms that can be used to find a maximum matching in non-bipartite graph is Edmonds’ Cardinality Matching Algorithm. Shrinking process is done in each blossom Bi that is encountered to become pseudovertex bi, in a way that each blossom does not interfere the process of finding a maximum matching in non-bipartite graph. In order to accelerate the finding, simple greedy method is used to perform initialization of matching and BFS algorithm is also used in constructing an alternating tree in a non-bipartite graph.The research discussed the finding of maximum  matching in non-bipartite graph using Edmonds’ cardinality matching algorithm. In addition, this research gave a sample of its application in the resolution of The Battle of Britain case. The result obtained is a maximum matching in non-bipartite graph. The maximum matching obtained is a solution to the case of The Battle of Britain.


Keywords


Edmonds’ cardinality matching, maximum matching, The Battle of Britain

Full Text:

PDF

References


Bondy, J. A., And Murty, U. S. R., 1976, Graph Theory with Applications, New York: Mac Millan Press.

Chartrand, G., And Lesniak, L., 1996, graph dan digraphs (third edition), London: Chapman dan Hill.

Edmons, Jack, 1965, paths, trees, and flowers, canadian j.math., 17, 449-467.

Evans, James R., and Edward Minieka, 1992, Optimization Algorithms for Networks and Graphs, New York: Marcel Dekker, Inc.

Gondran, M., and M. Minoux, 1984, Graphs and Algorithms, New York: Jhon Wiley & Sons.

Gross, Jonathan L., and Jay Yellen (Editors), 1999, Handbook of Graph Theory, USA: CRC Press.

Jungnickel, Dieter, 2008, Graphs, Networks, and Algorithms (Third Edition), Berlin: Springer – Verlag.

Lovasz, L., and M. D. Plummer, 1986, Matching Theory, USA: North – Holland.

Winter, 2005, Maximum Matching, CS105, www.cs.dartmouth.edu/~ac/Teach/CS105.../kavathekar-scribe.pdf

Zwick, U., 2009, Maximum Matching in Bipartite and Non-bipartite Graphs, http://www.cs.tau.ac.il/~zwick/grad-algo-0910/match.pdf




DOI: https://doi.org/10.18860/ca.v5i4.4294

Refbacks

  • There are currently no refbacks.


Copyright (c) 2019 Muchammad Abrori, Mohammad Imam Jauhari

Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

Editorial Office
Mathematics Department,
Universitas Islam Negeri Maulana Malik Ibrahim Malang
Gajayana Street 50 Malang, East Java, Indonesia 65144
Faximile (+62) 341 558933
e-mail: cauchy@uin-malang.ac.id

Creative Commons License
CAUCHY: Jurnal Matematika Murni dan Aplikasi is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.