Dynamics of heuristic optimization algorithms on random graphs

Details Dynamics of heuristic optimization algorithms on random graphs Dynamics of heuristic optimization algorithms on random graphs

2002-03-13

arxiv.org/abs/cond-mat/0203281v2

Eur. Phys. J. B 28, 369 (2002)

Physics

Condensed Matter

Statistical Mechanics

19 pages, 3 figures, version to app. in EPJ B

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Dynamics of heuristic optimization algorithms on random graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Dynamics of heuristic optimization algorithms on random graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Dynamics of heuristic optimization algorithms on random graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-252287