Maximum matching on random graphs

Details Maximum matching on random graphs Maximum matching on random graphs

2003-09-15

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

Physics

Condensed Matter

Disordered Systems and Neural Networks

7 pages with 2 eps figures included. Use EPL style. Submitted to Europhysics Letters

Scientific paper

The maximum matching problem on random graphs is studied analytically by the cavity method of statistical physics. When the average vertex degree \mth{c} is larger than \mth{2.7183}, groups of max-matching patterns which differ greatly from each other {\em gradually} emerge. An analytical expression for the max-matching size is also obtained, which agrees well with computer simulations. Discussion is made on this {\em continuous} glassy phase transition and the absence of such a glassy phase in the related minimum vertex covering problem.

Affiliated with

Also associated with

No associations

Rating

Maximum matching on 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 Maximum matching on random graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Maximum matching on random graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-510986