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 78
- Downloads 0
Inverted Pendulum-type Personal Mobility Considering Human Vibration Sensitivity
An inverted pendulum-type PM (personal mobility) has been attracting attention as a low-carbon vehicle. For many people who like to use the PM, ride comfort is important. However, ride comfort of PM has not been focused...
A Comparative Study of Thresholding Algorithms on Breast Area and Fibroglandular Tissue
One of the independently risk factors of breast cancer is mammographic density reflecting the composition of the fibroglandular tissue in breast area. Tumor in the mammogram is precisely complicated to detect as it is co...
Neural Network Based Lna Design for Mobile Satellite Receiver
Paper presents a Neural Network Modelling approach to microwave LNA design. To acknowledge the specifications of the amplifier, Mobile Satellite Systems are analyzed. Scattering parameters of the LNA in the frequency ran...
Redundancy Level Impact of the Mean Time to Failure on Wireless Sensor Network
Recently, wireless sensor networks (WSNs) have gained a great attention due to their ability to monitor various environments, such as temperature, pressure sound, etc. They are constructed from a large number of sensor n...
Line of Sight Estimation Accuracy Improvement using Depth Image and Ellipsoidal Model of Cornea Curvature
Line of sight estimation accuracy improvement is attempted using depth image (distance between user and display) and ellipsoidal model (shape of user’s eye) of cornea curvature. It is strongly required to improve line of...