A Novel Edge Cover based Graph Coloring Algorithm
Journal Title: International Journal of Advanced Computer Science & Applications - Year 2017, Vol 8, Issue 5
Abstract
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.
Authors and Affiliations
Harish Patidar, Dr. Prasun Chakrabarti
Keywords
Related Articles
- EP ID EP258775
- DOI 10.14569/IJACSA.2017.080534
- Views 80
- Downloads 0
Repository System for Geospatial Software Development and Integration
The integration of geospatial software components has recently received considerable attention due to the need for rapid growth of GIS application and development environments. However, finding appropriate source code co...
Review of Energy Reduction Techniques for Green Cloud Computing
The growth of cloud computing has led to uneconomical energy consumption in data processing, storage, and communications. This is unfriendly to the environment, because of the carbon emissions. Therefore, green IT is req...
Efficient Model for Distributed Computing based on Smart Embedded Agent
Technological advances of embedded computing exposed humans to an increasing intrusion of computing in their day-to-day life (e.g. smart devices). Cooperation, autonomy, and mobility made the agent a promising mechanism...
Comprehensive Classification Model for Diagnosing Multiple Disease Condition from Chest X-Ray
Classification plays a significant role in the diagnosis of any form of radiological images in the healthcare sector. After reviewing existing classification approaches carried out over chest radiographs, it was explored...
Reviewing Diagnosis Solutions for Valid Product Configurations in the Automated Analysis of Feature Models
A Feature Model (FM) is an information model to represent commonalities and variabilities for all the products of a Software Product Line (SPL). The complexity and large-scale of real feature models makes their manual an...