文章基本信息

标题：A Low Complexity based Edge Color Matching Algorithm for Regular Bipartite Multigraph
本地全文：下载
作者：Rezaul Karim ; Muhammad Mahbub Hasan Rony ; Md. Rashedul Islam 等
期刊名称：International Journal of Advanced Computer Science and Applications(IJACSA)
印刷版ISSN：2158-107X
电子版ISSN：2156-5570
出版年度：2017
卷号：8
期号：3
DOI：10.14569/IJACSA.2017.080335
出版社：Science and Information Society (SAI)
摘要：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.
关键词：thesai; IJACSA Volume 8 Issue 3; matching; edge-coloring; complexity; bipartite multigraph; DFS