GRAPH COLORING
NGC ALGORITHM
Dr. Ayan Seal By
CS206 Avinash, Rahul Jain, Rajat Kumar
What is Graph Coloring?
Graph coloring is a simple way of labelling graph
components such as vertices, edges, and regions
under some constraints.
In a graph, no two adjacent vertices, adjacent
edges, or adjacent regions are colored with
minimum number of colors.
Chromatic Number
The smallest number of colors needed to color a graph.
One of the Karp’s 21 NP-Complete Problem
Applications
Data mining
Image segmentation
Time Table Scheduling
Register Allocations
Bipartite Graphs
Networking
Clustering
Map Coloring
Our Application Area
Exam Time Table Scheduling
Why?
Problem we personally face more often
Most common problem in Schools/Universities
Boon For Time Table Management Department
Problem
Clash is the buzzword
Research Paper
A Novel Scheme for Graph Coloring - Vishal Donderia, Prasanta K. Jana
• C3IT 2012
• Department of Computer Science and Engineering
Indian School of Mines, Dhanbad-826 004, India
Why this paper?
Efficient with respect to
• Simplicity
• Robustness
• Computation Time
Problem
Prepare an Exam Schedule for the students enrolled in the following courses
with minimum number of slots without any CLASH.
Vertex Course
1 CS203
2 CS204
3 CS205
4 CS206
5 EC203
6 EC204
7 EC205
8 EC206
9 ME203
10 ME204
11 ME205
12 ME206
13 ES205
14 MS201
Implementation(NGC Algorithm)
2 1 12 11
3 10
13
4 9
14
5 8
6 7
Adjacency Matrix
1 2 3 4 5 6 7 8 9 10 11 12 13 14
1 0 1 1 1 0 0 0 0 0 0 0 0 1 1
2 1 0 1 1 0 0 0 0 0 0 0 0 1 1
3 1 1 0 1 0 0 0 0 0 0 0 0 1 1
4 1 1 1 0 0 0 0 0 0 0 0 0 1 1
5 0 0 0 0 0 1 1 1 0 0 0 0 1 1
6 0 0 0 0 1 0 1 1 0 0 0 0 1 1
7 0 0 0 0 1 1 0 1 0 0 0 0 1 1
8 0 0 0 0 1 1 1 0 0 0 0 0 1 1
9 0 0 0 0 0 0 0 0 0 1 1 1 1 1
10 0 0 0 0 0 0 0 0 1 0 1 1 1 1
11 0 0 0 0 0 0 0 0 1 1 0 1 1 1
12 0 0 0 0 0 0 0 0 1 1 1 0 1 1
13 1 1 1 1 1 1 1 1 1 1 1 1 0 1
14 1 1 1 1 1 1 1 1 1 1 1 1 1 0
Implementation(NGC Algorithm)
color[N]
• Colors to be assigned initially
• Array
flag[N]
• 1 if Colored with respective color in Color Array
• 0 if Not colored with respective color
• Array
color-assigned[N]
• Solution
• Color assigned to the vertex
• Array
Slots
Color Slot
1 Monday
2 Tuesday
3 Wednesday
4 Thursday
5 Friday
6 Saturday
Implementation(NGC Algo)
Step : 1
Vertex 1 2 3 4 5 6 7 8 9 10 11 12 13 14
Color 1 2 3 4 5 6 7 8 9 10 11 12 13 14
Flag 1 0 0 0 0 0 0 0 0 0 0 0 0 0
Color 1 0 0 0 0 0 0 0 0 0 0 0 0 0
assigned
Step : 2
Vertex 1 2 3 4 5 6 7 8 9 10 11 12 13 14
Color 1 2 3 4 5 6 7 8 9 10 11 12 13 14
Flag 0 0 0 0 0 0 0 0 0 0 0 0 0 0
Color 1 0 0 0 0 0 0 0 0 0 0 0 0 0
assigned
Implementation(NGC Algo)
Step : 3
Vertex 1 2 3 4 5 6 7 8 9 10 11 12 13 14
Color 1 2 3 4 5 6 7 8 9 10 11 12 13 14
Flag 1 0 0 0 0 0 0 0 0 0 0 0 0 0
Color 1 0 0 0 0 0 0 0 0 0 0 0 0 0
assigned
Step : 4
Vertex 1 2 3 4 5 6 7 8 9 10 11 12 13 14
Color 1 2 3 4 5 6 7 8 9 10 11 12 13 14
Flag 1 0 0 0 0 0 0 0 0 0 0 0 0 0
Color 1 2 0 0 0 0 0 0 0 0 0 0 0 0
assigned
Implementation(NGC Algorithm)
Step : 5
Vertex 1 2 3 4 5 6 7 8 9 10 11 12 13 14
Color 1 2 3 4 5 6 7 8 9 10 11 12 13 14
Flag 0 0 0 0 0 0 0 0 0 0 0 0 0 0
Color 1 2 0 0 0 0 0 0 0 0 0 0 0 0
assigned
Result
Time Complexity : O(n^3)
Final Solution
2 1 12 11
3 10
13
4 9
14
5 8
6 7
Suggestions
Error in the paper
C[2][k] = 0 instead of C[1][k]
Limitation
Colors assigned initially is same as the number of vertices.
• Although we need less colors to color the graph
Conclusion
Thank You!
