Copyright Statement: This is an open access article licensed under a Creative Commons Attribution 4.0 International License, which permits unrestricted use, distribution, and reproduction in any medium, even commercially as long as the original work is properly cited.
Digital Object Identifier (DOI) : 10.14569/IJACSA.2017.080335
Article Published in International Journal of Advanced Computer Science and Applications(IJACSA), Volume 8 Issue 3, 2017.
Abstract: An edge coloring of a graph G is a process of assigning colors to the adjacent edges so that the adjacent edges represents the different colors. In this paper, an algorithm is proposed to find the perfect color matching of the regular bipartite multigraph with low time complexity. For that, the proposed algorithm is divided into two procedures. In the first procedure, the possible circuits and bad edges are extracted from the regular bipartite graph. In the second procedure, the bad edges are rearranged to obtain the perfect color matching. The depth first search (DFS) algorithm is used in this paper for traversing the bipartite vertices to find the closed path, open path, incomplete components, and bad edges. By the proposed algorithm, the proper edge coloring of D – regular bipartite multi-graph can be obtained in O (D.V) time.
Rezaul Karim, Muhammad Mahbub Hasan Rony, Md. Rashedul Islam and Md. Khaliluzzaman, “A Low Complexity based Edge Color Matching Algorithm for Regular Bipartite Multigraph ” International Journal of Advanced Computer Science and Applications(IJACSA), 8(3), 2017. http://dx.doi.org/10.14569/IJACSA.2017.080335