Analysis of the mean field annealing algorithm for graph colouring
John S. Shawe-Taylor, Janez Žerovnik · ePrints Soton (University of Southampton) · 1996
The operation of the MFA algorithm for a Generalised Boltzmann Machine is characterised by the definition of an appropriate energy function which the algorithm attempts to minimise. The case of graph colouring is studied in detail and a relationship between the critical temperature of the MFA algorithm and the minimal eigenvalue of the graph to be coloured is demonstrated. Experimental results are presented which indicate that in both a massively parallel implementation and in a sequential implementation the algorithm outperforms the Petford and Welsh algorithm on random graphs. The experiments, however, suggest that the algorithm is less effective for graphs that are difficult to colour.