The Study of Vertex Coloring Algorithms Using Heuristic Approaches

Please use this identifier to cite or link to this item: http://drsr.daiict.ac.in//handle/123456789/731

Title:	The Study of Vertex Coloring Algorithms Using Heuristic Approaches
Authors:	Muthu, Rahul Lodha, Pratik
Keywords:	Algorithms Vertex Coloring Graph Kneser Lines Graph Harary Line Graph Hyper-cube Line Graph Star Line Graph Path Line Graph Wheel Line Graph Machine Learning
Issue Date:	2018
Publisher:	Dhirubhai Ambani Institute of Information and Communication Technology
Citation:	Lodha, Pratik (2018). The Study of Vertex Coloring Algorithms Using Heuristic Approaches. Dhirubhai Ambani Institute of Information and Communication Technology, v, 30 p. (Acc. No: T00687)
Abstract:	Graph vertex coloring is one of the most studied NP-complete optimization problem (READ, 1972) [2]. The problem is that; given a graph G, determine the number of colors required to color G, so that no two adjacent vertices share the same color. And the minimum number of colors required to color graph is known as Chromatic Number and is denoted by ?(G). By using existing properties of eccentricity, BFS, DFS (West, 2000) [3] and graph components we have proposed three new heuristic algorithms to obtain approximated chromatic number of a given graph G. And these approaches are as follows: 1. Eccentricity based coloring 2. DFS based coloring, and 3. Maximum degree based coloring.
URI:	http://drsr.daiict.ac.in//handle/123456789/731
Appears in Collections:	M Tech Dissertations

Files in This Item:

File	Description	Size	Format
201611016_Pratik Lodha.pdf	201611016	1.14 MB	Adobe PDF	View/Open

DSpace JSPUI