Vertex cover problem studied by cavity method: Analytics and population dynamics

Details Vertex cover problem studied by cavity method: Analytics and population dynamics Vertex cover problem studied by cavity method: Analytics and population dynamics

2003-02-14

arxiv.org/abs/cond-mat/0302289v1

European Physical Journal B 32: 265-270 (2003)

Physics

Condensed Matter

Statistical Mechanics

7 pages (including 3 figures and 1 table), REVTeX4 format

Scientific paper

10.1140/epjb/e2003-00096-4

We study the vertex cover problem on finite connectivity random graphs by zero-temperature cavity method. The minimum vertex cover corresponds to the ground state(s) of a proposed Ising spin model. When the connectivity c>e=2.718282, there is no state for this system as the reweighting parameter y, which takes a similar role as the inverse temperature \beta in conventional statistical physics, approaches infinity; consequently the ground state energy is obtained at a finite value of y when the free energy function attains its maximum value. The minimum vertex cover size at given c is estimated using population dynamics and compared with known rigorous bounds and numerical results. The backbone size is also calculated.

Affiliated with

Also associated with

No associations

Rating

Vertex cover problem studied by cavity method: Analytics and population dynamics 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 Vertex cover problem studied by cavity method: Analytics and population dynamics, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Vertex cover problem studied by cavity method: Analytics and population dynamics will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-267128