"Algorithms and Experiments on Colouring Squares of Planar Graphs"


Ομιλητής: Ανδρέου Μαρία
Υποψήφια Διδάκτωρ του Τμήματος Η/Υ & Πληροφορικής του Πανεπιστήμίου Πατρών και μέλος της ΕΜ1 του ΕΑΙΤΥ

Περίληψη: In this work we study the important problem of {\em colouring} {\em squares of planar graphs} (SQPG). We design and implement {\em two new algorithms} that colour in a different way SQPG. We call these algorithms $MDsatur$ and $RC$. We have also implemented and experimentally evaluated the performance of most of the known approximation colouring algorithms for SQPG [MS02,FNPS00,AH00,HM99]. We compare the quality of the colourings achieved by these algorithms, with the colourings obtained by our algorithms and with the results obtained from two well-known {\em greedy colouring heuristics}. The heuristics are mainly used for comparison reasons and unexpectedly give very good results. Our algorithm $MDsatur$ outperforms the known algorithms as shown by the extensive experiments we have carried out. The planar graph instances whose squares are used in our experiments are ``non-extremal" graphs obtained by LEDA and hard colourable graph instances that we construct. The most interesting conclusions of our experimental study are: 1) all colouring algorithms considered here have {\em almost optimal} performance on the squares of ``{\em non-extremal}" planar graphs. 2) all known colouring algorithms especially designed for colouring SQPG, give {\em significantly better} results, even on hard to colour graphs, when the vertices of the input graph are {\em randomly named}. On the other hand, the performance of our algorithm, $MDsatur$, becomes worse in this case, however it still has the best performance compared to the others. $MDsatur$ colours the tested graphs with $1.1\,OPT$ colours in most of the cases, even on hard instances, where $OPT$ denotes the number of colours in an optimal colouring. 3) we {\em construct worst case instances} for the algorithm of Fotakis el al.\cite{FNPS00}, which show that {\em its theoretical analysis is tight}.