Simulated Annealing and Graph Colouring

Nolte, Andreas and Schrader, Rainer (2001) Simulated Annealing and Graph Colouring.
Published in: Combinatorics, probability & computing Vol. 10 (1). 29 -40.


Simulated Annealing is a very successful heuristic for various problems in combinatorial optimization. In this paper an application of Simulated Annealing to the 3-coloring problem is considered. In contrast to many good empirical results we will show for a certain class of graphs that the expected first hitting time of a proper coloring, given an arbitrary cooling scheme, is of exponential size. These results are complementary to those in "Nolte, Andreas and Schrader, Rainer (2000) A Note on the Finite Time Behaviour of Simulated Annealing", where the convergence of Simulated Annealing to an optimal solution in exponential time is proved.

Download: [img] Postscript - Preprinted Version
Download (478kB) | Preview
Editorial actions: View Item View Item (Login required)
Deposit Information:
ZAIK Number: zaik1999-348
Depositing User: Rainer Schrader
Date Deposited: 02 Apr 2001 00:00
Last Modified: 04 Jul 2014 13:15