LOGIN
>> Home
>> Topics
>> Students
>> Partners
>> Statistics


Information for topics

Topic Id:
ID topic: 217
Partner Email: stavros@cs.uoi.gr
Project Title: Construction Algorithms and Study of Coloring Problems on Perfect Graphs
Abstract: The objective of this thesis is to design and implement algorithms, to construct perfect graphs and also to study and implement coloring algorithms for perfect graphs. A graph coloring in its simplest form is the assignment of colors to the graph vertices, such that all adjacent vertices have different colors. It is well-known that coloring of arbitrary graphs belongs to the class of NP-complete problems. For this reason several heuristic methods have been developed that approximate the chromatic number of an arbitrary graph. In this thesis, we study heuristic coloring methods, such as the Sequential algorithm and some of its variants, such as Largest First, Smaller Last and Color Degree
Advisor: Stavros Nikolopoulos
Link:
Degree: Master
 Keywords: