Dynamics of heuristic optimization algorithms on random graphs |
| |
Authors: | M Weigt |
| |
Institution: | Institute for Theoretical Physics, University of G?ttingen, Bunsenstr. 9, 37073 G?ttingen, Germany, DE
|
| |
Abstract: | In this paper, the dynamics of heuristic algorithms for constructing small vertex covers (or independent sets) of finite-connectivity
random graphs is analysed. In every algorithmic step, a vertex is chosen with respect to its vertex degree. This vertex, and
some environment of it, is covered and removed from the graph. This graph reduction process can be described as a Markovian
dynamics in the space of random graphs of arbitrary degree distribution. We discuss some solvable cases, including algorithms
already analysed using different techniques, and develop approximation schemes for more complicated cases. The approximations
are corroborated by numerical simulations.
Received 14 March 2002 Published online 31 July 2002 |
| |
Keywords: | PACS 89 20 -a Interdisciplinary applications of physics – 02 50 -r Probability theory stochastic processes and statistics – 89 20 Ff Computer science and technology |
本文献已被 SpringerLink 等数据库收录! |
|