文章基本信息

标题：A Novel Edge Cover based Graph Coloring Algorithm
本地全文：下载
作者：Harish Patidar ; Dr. Prasun Chakrabarti
期刊名称：International Journal of Advanced Computer Science and Applications(IJACSA)
印刷版ISSN：2158-107X
电子版ISSN：2156-5570
出版年度：2017
卷号：8
期号：5
DOI：10.14569/IJACSA.2017.080534
出版社：Science and Information Society (SAI)
摘要：Graph Colouring Problem is a well-known NP-Hard problem. In Graph Colouring Problem (GCP) all vertices of any graph must be coloured in such a way that no two adjacent vertices are coloured with the same colour. In this paper, a new algorithm is proposed to solve the GCP. Proposed algorithm is based on finding vertex sets using edge cover method. In this paper implementation prospective of the algorithm is also discussed. Implemented algorithm is tested on various graph instances of DIMACS standards dataset. Algorithm execution time and a number of colours required to colour graph are compared with some other well-known Graph Colouring Algorithms. Variation in time complexity with reference to increasing in the number of vertices, a number of edges and an average degree of a graph are also discussed in this paper.
关键词：Graph Colouring Problem; Edge Cover; Independent Set; NP-Hard Problem