The Study of Vertex Coloring Algorithms Using Heuristic Approaches

Simple item page
dc.accession.numberT00687
dc.classification.ddc006.31 LOD
dc.contributor.advisorMuthu, Rahul
dc.contributor.authorLodha, Pratik
dc.date.accessioned2019-03-19T09:30:50Z
dc.date.accessioned2025-06-28T10:19:18Z
dc.date.available2019-03-19T09:30:50Z
dc.date.issued2018
dc.degreeM. Tech
dc.description.abstractGraph 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.
dc.identifier.citationLodha, 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)
dc.identifier.urihttp://drsr.daiict.ac.in/handle/123456789/731
dc.publisherDhirubhai Ambani Institute of Information and Communication Technology
dc.student.id201611016
dc.subjectAlgorithms
dc.subjectVertex Coloring
dc.subjectGraph
dc.subjectKneser Lines Graph
dc.subjectHarary Line Graph
dc.subjectHyper-cube Line Graph
dc.subjectStar Line Graph
dc.subjectPath Line Graph
dc.subjectWheel Line Graph
dc.subjectMachine Learning
dc.titleThe Study of Vertex Coloring Algorithms Using Heuristic Approaches
dc.typeDissertation

Files

Original bundle

Now showing 1 - 1 of 1
Thumbnail Image
Name:
201611016_Pratik Lodha.pdf
Size:
1.11 MB
Format:
Adobe Portable Document Format
Description:
201611016
Download

Collections

M Tech Dissertations