%0 Journal Article
%T Problem of Maximum Matching in Non-Bipartite Graph Using Edmonds¡¯ Cardinality Matching Algorithm and Its Applicationin the Battle of Britain Case
%A Mohammad Imam Jauhari
%A Muchammad Abrori
%J -
%D 2019
%R http://dx.doi.org/10.18860/ca.v5i4.4294
%X 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
%K Edmonds¡¯ cardinality matching
%K maximum matching
%K The Battle of Britain
%U http://ejournal.uin-malang.ac.id/index.php/Math/article/view/4294