Message passing for vertex covers

Details Message passing for vertex covers Message passing for vertex covers

2006-05-08

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

Phys. Rev. E 74, 046110 (2006)

Physics

Condensed Matter

Statistical Mechanics

25 pages, 9 figures - version accepted for publication in PRE

Scientific paper

10.1103/PhysRevE.74.046110

Constructing a minimal vertex cover of a graph can be seen as a prototype for a combinatorial optimization problem under hard constraints. In this paper, we develop and analyze message passing techniques, namely warning and survey propagation, which serve as efficient heuristic algorithms for solving these computational hard problems. We show also, how previously obtained results on the typical-case behavior of vertex covers of random graphs can be recovered starting from the message passing equations, and how they can be extended.

Affiliated with

Also associated with

No associations

Rating

Message passing for vertex covers 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 Message passing for vertex covers, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Message passing for vertex covers will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-463189