Physics – Condensed Matter – Statistical Mechanics
Scientific paper
2000-06-21
Theoretical Computer Science 265, 199 (2001)
Physics
Condensed Matter
Statistical Mechanics
24 pages, 9 figures
Scientific paper
The vertex-cover problem is studied for random graphs $G_{N,cN}$ having $N$ vertices and $cN$ edges. Exact numerical results are obtained by a branch-and-bound algorithm. It is found that a transition in the coverability at a $c$-dependent threshold $x=x_c(c)$ appears, where $xN$ is the cardinality of the vertex cover. This transition coincides with a sharp peak of the typical numerical effort, which is needed to decide whether there exists a cover with $xN$ vertices or not. For small edge concentrations $c\ll 0.5$, a cluster expansion is performed, giving very accurate results in this regime. These results are extended using methods developed in statistical physics. The so called annealed approximation reproduces a rigorous bound on $x_c(c)$ which was known previously. The main part of the paper contains an application of the replica method. Within the replica symmetric ansatz the threshold $x_c(c)$ and the critical backbone size $b_c(c)$ can be calculated. For $c
Hartmann Alexander K.
Weigt Martin
No associations
LandOfFree
Statistical mechanics perspective on the phase transition in vertex covering finite-connectivity 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 Statistical mechanics perspective on the phase transition in vertex covering finite-connectivity random graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Statistical mechanics perspective on the phase transition in vertex covering finite-connectivity random graphs will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-22676