https://doi.org/10.1140/epjb/e2002-00240-8
Dynamics of heuristic optimization algorithms on random graphs
Institute for Theoretical Physics,
University of Göttingen, Bunsenstr. 9, 37073 Göttingen, Germany
Corresponding author: a weigt@theorie.physik.uni-goettingen.de
Received:
14
March
2002
Published online:
31
July
2002
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.
PACS: 89.20.-a – Interdisciplinary applications of physics / 02.50.-r – Probability theory, stochastic processes, and statistics / 89.20.Ff – Computer science and technology
© EDP Sciences, Società Italiana di Fisica, Springer-Verlag, 2002
