Maximum matching on random graphs

Abstract

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.

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

Cited by in corpus (10)

• Control Principles of Complex Networks
• Exact Controllability of Complex Networks
• The number of matchings in random graphs
• Core percolation on complex networks
• Controllability and maximum matchings of complex networks
• Statistical mechanics of dimers on quasiperiodic Ammann-Beenker tilings
• Long range frustration in finite connectivity spin glasses: A mean field theory and its application to the random $K$-satisfiability problem
• Statistical mechanics of bipartite $z$-matchings
• A local algorithm and its percolation analysis of bipartite $z$-matching problem
• Reduce the rank calculation of a high-dimensional sparse matrix based on network controllability theory