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 97
- Downloads 0
Tree-Combined Trie: A Compressed Data Structure for Fast IP Address Lookup
For meeting the requirements of the high-speed Internet and satisfying the Internet users, building fast routers with high-speed IP address lookup engine is inevitable. Regarding the unpredictable variations occurred in...
Identifying Green Services using GSLA Model for Achieving Sustainability in Industries
Green SLA (GSLA) is a formal agreement between service providers/vendors and users/customers incorporating all the traditional/basic commitments (Basic SLAs) as well as incorporating Ecological, Economical, and Ethical (...
Mobile Software Testing: Thoughts, Strategies, Challenges, and Experimental Study
Mobile devices have become more pervasive in our daily lives, and are gradually replacing regular computers to perform traditional processes like Internet browsing, editing photos, playing videos and sound track, and rea...
Trajectory based Arabic Sign Language Recognition
Deaf and hearing impaired people use their hand as a tongue to convey their thoughts by performing descriptive gestures that form the sign language. A sign language recognition system is a system that translates these ge...
Towards the Algorithmic Detection of Artistic Style
The artistic style of a painting can be sensed by the average observer, but algorithmically detecting a painting’s style is a difficult problem. We propose a novel method for detecting the artistic style of a painting th...