Physics – Condensed Matter – Statistical Mechanics
Scientific paper
2009-01-17
Physics
Condensed Matter
Statistical Mechanics
15 pages, 9 figures
Scientific paper
The vertex-cover problem is a prototypical hard combinatorial optimization problem. It was studied in recent years by physicists using the cavity method of statistical mechanics. In this paper, the stability of the finite-temperature replica-symmetric (RS) and the first-step replica-symmetry-broken (1RSB) cavity solutions of the vertex cover problem on random regular graphs of finite vertex-degree $K$ are analyzed by population dynamics simulations. We found that (1) the lowest temperature for the RS solution to be stable, $T_{RS}(K)$, is not a monotonic function of $K$, and (2) at relatively large connectivity $K$ and temperature $T$ slightly below the dynamic transition temperature $T_d(K)$, the 1RSB solutions with small but non-negative complexity values are stable. Similar results are obtained on random Poissonian graphs.
Zeng Ying
Zhang Pei-Pei
Zhou Hai-jun
No associations
LandOfFree
Stability analysis on the finite-temperature replica-symmetric and first-step replica-symmetry-broken cavity solutions of the random vertex cover problem 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 Stability analysis on the finite-temperature replica-symmetric and first-step replica-symmetry-broken cavity solutions of the random vertex cover problem, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Stability analysis on the finite-temperature replica-symmetric and first-step replica-symmetry-broken cavity solutions of the random vertex cover problem will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-119061