PACS. 89.20.-a Interdisciplinary applications of physics – 02.50.-r Probability theory, stochastic processes, and statistics – 89.20.Ff Computer science and technology
Springer Online Journal Archives 1860-2000
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.
Type of Medium: