LOGIN
>> Home
>> Topics
>> Students
>> Partners
>> Statistics
Information for topics
Topic Id:
ID topic:
218
Partner Email:
stavros@cs.uoi.gr
Project Title:
Experimental Study of Graph Coloring Algorithms
Abstract:
Graph Colouring is the procedure of colouring the nodes of a graph so that any two adjacent nodes do not have the same colour. In this thesis we will examine the behaviour of certain algorithms applied on perfect graphs, compared to the optimum colouring which is equivalent to the maximum graph clique. We examine the behaviour of the following algorithms: MDsatur, greedy First Fit and optimum colour. In particular, we study the following graphs: permutation graphs, interval graphs, triangular graphs, cographs, complements of permutation graphs and complements of interval graphs.
Advisor:
Stavros Nikolopoulos
Link:
Degree:
Master
Keywords:
