A Multilevel Approach to the Graph Colouring Problem

C. Walshaw


We motivate, derive and implement a multilevel approach to the graph colouring problem. The resulting algorithm progressively coarsens the problem, initialises a colouring and then employs either Culberson's iterated greedy algorithm or tabu search to refine the solution on each of the coarsened problems in reverse order. Tests on a large suite of problem instances indicate that for low-density graphs (up to around 30% edge density) the multilevel paradigm can either speed up (iterated greedy) or even improve (tabu search) the asymptotic convergence. This augments existing evidence that, although the multilevel framework cannot be considered as a panacea for combinatorial optimisation problems, it can provide a useful addition to the combinatorial optimisation toolkit.

Keywords: Multilevel Refinement; Graph Colouring; Combinatorial Optimisation.

Fri Aug 13 13:39:42 BST 2004