Maximum matching on random graphs

Thumbnail Image

Date

Authors

Journal Title

Journal ISSN

Volume Title

Publisher

Abstract

Description

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

Keywords

Disordered Systems and Neural Networks, Statistical Mechanics

Citation

URI

http://salesiana.dossiersoluciones.com/handle/123456789/22217

Consulte el texto completo en el siguiente enlace:

https://arxiv.org/abs/cond-mat/0309348
 http://arxiv.org/abs/cond-mat/0309348

Collections

arXiv