Archived: 11 February 2003
University of Adelaide Masters by coursework thesis, June 2002.
Supervisor: Paul Coddington
Graph colouring is very useful in many different kind of applications. The Graph Colouring Problem (GCP) itself -- which is known as an NP-hard problem -- is usually part of another large computation problem, therefore a good solution to the GCP is required. Much research has found solutions in the form of sequential algorithms, which are very useful for small scale graphs. In the case of large graphs, these sequential algorithms might cause a bottleneck in the overall computation, particularly if the rest of the computation is done in parallel. Hence, a parallel heuristic is required to improve the computation time for the GCP.
The lack of research on parallel heuristics of GCP has motivated us to seek a good solution for the problem. This project is aimed at implementing and comparing a variety of those sequential and parallel algorithms. Moreover, most of existing parallel algorithms have been implemented on distributed memory machines and typically give little or no speed-up. Therefore, the algorithms developed here is written in Java Thread and run on shared memory machine to achieve a good speed-up. A comparison of performance for different algorithms in different types and size of graphs is conducted to observe which algorithm is best for particular types of graphs.