## My Class “Graph Coloring” Got Innovation Award Nomination

I just got my class “Graph Coloring” nominated at phpclasses.org for the month of May, 2006. I am enjoying the times very much after getting this good news from PHP Classes authority.

Please see this class and vote me. This class implements a completely new graph coloring algorithm designed by me.

========== Read Me ===================================

What’s graph coloring:

In a connected graph (where vertices are connected e.g. no isolated vertex exists), graph coloring is the process that ensures proper marker (/color) has (/have) been assigned to a vertex so that no adjacent (connected) vertices hold the same marker (/color).

How this class works:

This class implemented a new algorithm of graph coloring. The present class works as follow:

1. Gets graph from source (file OR DB)

1. Represents the graph (connections as well) as an array

2. Traverses the array to color vertices according to the algorithm

3. Displays the color result

The New Graph Coloring Algorithm:

The new approach of graph coloring works as follow:

======================================

graph = graph array

i=1

j=1

while(i<=no_of_vertices)
while(j<=no_of_vertices)
if (graph[i][j]==1)
i. color vertex i, push it into the colored array
ii. process(i)
else
graph[i][j]:= 0;
endif
6. j++
End of while
7. i++
End of while
—————————————–
function process(j)
i=1
while(i<=no_of_vertices)
if(graph[j][i]==1)
(i). graph[j][i]:=0 //Disconnects the colered vertex j from its connected ones — duplex disconnection
(ii).Disconnects vertex i(which is connected to the newly colored vertex j)from its connected ones–simplex disconnection
endif
End of while
end of function
====================================
I am not giving the complexity analysis of this algorithm here. Future versions will come with so.
Best Regards,
[Rupom ]

Good job done bro. Keep up the good work and congratulations!

Thanks and God Bless!!

Ehsan

thanks for your support and inspirations.

Well done!! Congrates!!

Best Wishes for you

Thanks

Tahmid Munaz

Thanks Munaz.

Regards,

$Rupom

Congratulation for your excellent work.

I don’t know much about Graph coloring theory. As i know Graph coloring has many practical applications and theoretical challenges. For example coloring political map of the countries with “Four color theorem”. This is a very active field of research. As i found your class “Graph Coloring” in phpclasses.org, i want to know what will be application of this class. I am talking about web applications. Have you used “graph coloring” or any other graph theory in web applications that makes your life easier?

Keep it up. Best wishes for you.

Thanks

Riyadh Hossain

Hello Riyadh,

Thanks for your comment here. I am going to mention two uses of Graph Coloring.

1. Lets say a university has 100 courses and 1000 students. Many students have taken more than 1 courses in a semester/term. Now the university needs to schedule the exams for that semester/term in such a way that no students miss any exam. So what will be the solution?Graph Coloring is the perfect solution provider in that case. Soon I will provide the Open Source community another class that will schedule exams by Graph Coloring.

2. A big country has many regions. There is a govt. TV channel and it has substations in all the regions. Now if the central authority wants to make a broadcasting schedule so that no two consecutive stations can broadcast same function at a time. What will be the solution ? Graph Coloring is also solution provider here.

I didnt face such problems yet, but surely i will. I just thought such applications and such complexities. And discovered this solution in a new way.

Thanks again. Please visit my site regularly and comment for more suggestions and discovers. Your suggestions will be highly appreciated.

Regards,

MA Razzaque Rupom