An Algorithm Based on Heap of Binary Search Tree to Solve Graph Coloring Problem
Ajay Narayan Shukla1, Vishal Bharti2, M.L. Garg3
1Ajay Narayan Shukla, Department of Computer Science Engineering, Dehradun Institute of Technology University, Dehradun, India.
2Dr. Vishal Bharti, Department of Computer Science Engineering, Dehradun Institute of Technology University, Dehradun, India.
3Dr. M L Garg, Department of Computer Science Engineering, Dehradun Institute of Technology University, Dehradun, India.
Manuscript received on 11 March 2019 | Revised Manuscript received on 16 March 2019 | Manuscript published on 30 July 2019 | PP: 3920-3924 | Volume-8 Issue-2, July 2019 | Retrieval Number: B1793078219/19©BEIESP | DOI: 10.35940/ijrte.B1793.078219
Open Access | Ethics and Policies | Cite | Mendeley | Indexing and Abstracting
© The Authors. Blue Eyes Intelligence Engineering and Sciences Publication (BEIESP). This is an open access article under the CC-BY-NC-ND license (http://creativecommons.org/licenses/by-nc-nd/4.0/)
Abstract: Graph coloring problem is one of most frequent studied problem in the graph theory due to its uses in different area of applications like simulation of biological networks, communication networks, register allocation and many more. This problem involves the coloring of the vertices of the given a graph G (V, E) with number of available colors in such a manner that adjacent vertices must assign colors different with each other. In this paper we present a hybrid approach to assign the colors to vertices of the given graph that is based on adjacency matrix and search tree data structure. The coloring process for a particular vertex in the graph will done by getting the feasible colors available in the color list. The feasible colors that may be assigned to a vertex, retrieved from the vertex-color binary search tree generated initially for available colors. The proposed solution for the graph coloring problem is efficient in terms of its running time complexity and it will work without affecting its complexity for any kind of graph.
Index Terms: Adjacency Matrix, Graph Coloring, Hybrid Approach, Vertex-Color Binary Search Tree.
Scope of the Article: Web Algorithms