No CrossRef data available.
Simulated Annealing and Graph Colouring
Published online by Cambridge University Press: 12 April 2001
Abstract
Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.
Simulated annealing is a very successful heuristic for various problems in combinatorial optimization. In this paper an application of simulated annealing to the 3-colouring 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 colouring, given an arbitrary cooling scheme, is of exponential size.
These results are complementary to those in [13], where we prove the convergence of simulated annealing to an optimal solution in exponential time.
Information
- Type
- Research Article
- Information
- Copyright
- 2001 Cambridge University Press
Footnotes
Extended version of [14].
You have
Access