The number of guards needed by a museum: A phase transition in vertex covering of random graphs

Details The number of guards needed by a museum: A phase transition in vertex covering of random graphs The number of guards needed by a museum: A phase transition in vertex covering of random graphs

2000-01-11

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

Phys. Rev. Lett. 84, 6118 (2000)

Physics

Condensed Matter

Disordered Systems and Neural Networks

4 pages, 3 eps-figures, new version to be published in Phys. Rev. Let

Scientific paper

10.1103/PhysRevLett.84.6118

In this letter we study the NP-complete vertex cover problem on finite connectivity random graphs. When the allowed size of the cover set is decreased, a discontinuous transition in solvability and typical-case complexity occurs. This transition is characterized by means of exact numerical simulations as well as by analytical replica calculations. The replica symmetric phase diagram is in excellent agreement with numerical findings up to average connectivity $e$, where replica symmetry becomes locally unstable.

Affiliated with

Also associated with

No associations

Rating

The number of guards needed by a museum: A phase transition in vertex covering of 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 The number of guards needed by a museum: A phase transition in vertex covering of random graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The number of guards needed by a museum: A phase transition in vertex covering of random graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-364589