The Study of Vertex Coloring Algorithms Using Heuristic Approaches
Graph vertex coloring is one of the most studied NP-complete optimization problem (READ, 1972) . 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)  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.
- M Tech Dissertations 
Showing items related by title, author, creator and subject.
Vaishnav, Nileshkumar (Dhirubhai Ambani Institute of Information and Communication Technology, 2018)Real-world data such as weather data, seismic activity data, sensor networks data and social network data can be represented and processed conveniently using a mathematical structure called Graph. Graphs are a collection ...
Teja, V. Krishna (Dhirubhai Ambani Institute of Information and Communication Technology, 2011)An acyclic edge coloring of a graph G is a proper edge coloring of G which has no dichromatic cycle. The minimum number of colors required to acyclically edge color graph G is called its acyclic chromatic index, denoted ...
Desai, Abhi Hitesh (Dhirubhai Ambani Institute of Information and Communication Technology, 2013)A shock graph is an abstraction of a two-dimensional shape of an object. It represents the shape as a graph, using its boundary information. In this thesis, we study the shock graph representation of two-dimensional shapes. ...