sis 18: e12

Research Article

A Greedy Technique Based Improved Approach to Solve Graph Colouring Problem

Download25 downloads
  • @ARTICLE{10.4108/eai.16-2-2021.168716,
        author={Ajay Narayan Shukla and Vishal Bharti and M. L. Garg},
        title={A Greedy Technique Based Improved Approach to Solve Graph Colouring Problem},
        journal={EAI Endorsed Transactions on Scalable Information Systems: Online First},
        volume={},
        number={},
        publisher={EAI},
        journal_a={SIS},
        year={2021},
        month={2},
        keywords={Graph Colouring, Adjacency Matrix, Greedy Technique, Colour Matrix},
        doi={10.4108/eai.16-2-2021.168716}
    }
    
  • Ajay Narayan Shukla
    Vishal Bharti
    M. L. Garg
    Year: 2021
    A Greedy Technique Based Improved Approach to Solve Graph Colouring Problem
    SIS
    EAI
    DOI: 10.4108/eai.16-2-2021.168716
Ajay Narayan Shukla1,*, Vishal Bharti1, M. L. Garg1
  • 1: DIT University, Dehradun-India, Department of CSE
*Contact email: ajayshuk@gmail.com

Abstract

Graph colouring problem is a well-known NP-class optimization problem, studied due to a lot of applications in various real-world problems. Some of these applications are: register allocation, image processing and communication networks. There are various techniques suggested by the researchers to solve the problem which is either exact or approximate in nature. In this paper, a new greedy technique, based on degrees of vertices in the graph is presented to solve the graph colouring problem in an improved manner. The technique involves the use of adjacency matrix along with another matrix generated for the set of possible colours for each vertex in the graph. The generated colour matrix is used to assign the colours among the vertices in the graph based on decreasing degrees of the vertices. Several DIMACS colouring instances solved using the suggested approach in the article and compared with some contemporary techniques for the performance and proves compatible and having better execution time with compared technique. The obtained colouing results are mostly optimal colour values corresponding to the examined colouring instances of the graph.