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 85
- Downloads 0
MOMEE: Manifold Optimized Modeling of Energy Efficiency in Wireless Sensor Network
Although adoption pace of wireless sensor network has increased in recent times in many advance technologies of ubiquitous-ness, but still there are various open-end challenges associated with energy efficiencies among t...
Efficient Threshold Signature Scheme
In this paper, we introduce a new threshold signature RSA-typed scheme. The proposed scheme has the characteristics of un-forgeable and robustness in random oracle model. Also, signature generation and verificatio...
A Novel Permutation Based Approach for Effective and Efficient Representation of Face Images under Varying Illuminations
Paramount importance for an automated face recognition system is the ability to enhance discriminatory power with a low-dimensional feature representation. Keeping this as a focal point, we present a novel approach for f...
Developing an Algorithm for Securing the Biometric Data Template in the Database
In the current technology advancement, biometric template provides a dependable solution to the problem of user verification in an identity control system. The template is saved in the database during the enrollment and...
On the Dynamic Maintenance of Data Replicas based on Access Patterns in A Multi-Cloud Environment
Cloud computing provides services and infrastructures to enable end-users to access, modify and share massive geographically distributed data. There are increasing interests in developing data-intensive (big data) applic...