Maximum matching on random graphs
Zhou, Haijun · Ou-Yang, Zhong-can
Original · EN
The maximum matching problem on random graphs is studied analytically by the cavity method of statistical physics. When the average vertex degree c is larger than 2.7183, groups of max-matching patterns which differ greatly from each other gradually emerge. An analytical expression for the max-matching size is also obtained, which agrees well with computer simulations. Discussion is made on this continuous glassy phase transition and the absence of such a glassy phase in the related minimum vertex covering problem.
English translation
This paper has no Arabic translation yet. Be the first: it takes a few seconds, and the result is stored for every future reader.