Nolte, Andreas and Schrader, Rainer (2001). Simulated Annealing and Graph Colouring. Combinatorics, probability & computing, 10 (1). 29 -40. Cambridge Univ. Press.

[thumbnail of zaik1999-348.pdf]
Preview
 PDF
zaik1999-348.pdf - Draft Version
Download (234kB) | Preview

Abstract

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.

Item Type: Article
Creators:
Creators
Email
ORCID
ORCID Put Code
Nolte, Andreas
UNSPECIFIED
UNSPECIFIED
UNSPECIFIED
Schrader, Rainer
UNSPECIFIED
UNSPECIFIED
UNSPECIFIED
URN: urn:nbn:de:hbz:38-548345
Journal or Publication Title: Combinatorics, probability & computing
Volume: 10
Number: 1
Page Range: 29 -40
Date: 2001
Publisher: Cambridge Univ. Press
Language: English
Faculty: Faculty of Mathematics and Natural Sciences
Divisions: Faculty of Mathematics and Natural Sciences > Department of Mathematics and Computer Science > Institute of Computer Science
Subjects: Data processing Computer science
Refereed: No
URI: http://kups.ub.uni-koeln.de/id/eprint/54834

Downloads

Downloads per month over past year

Export

Actions (login required)

View Item View Item