|
|||||
|
|
Phase Transitions for the Cavity Approach to the Clique Problem on Random Graphs |
|
| Authors: | Alexandre Gaudillière Benedetto Scoppola Elisabetta Scoppola Massimiliano Viale |
| Institution: | 1.LATP, CNRS,Université de Provence,Marseille,France;2.Dipartimento di Matematica,University of Rome “Tor Vergata”,Rome,Italy;3.Dipartimento di Matematica,University of Rome “Roma Tre”,Rome,Italy;4.Dipartimento di Fisica,University of Rome “La Sapienza”,Rome,Italy |
| Abstract: | We give a rigorous proof of two phase transitions for a disordered statistical mechanics system used to define an algorithm to find large cliques inside Erdös random graphs. Such a system is a conservative probabilistic cellular automaton inspired by the cavity method originally introduced in spin glass theory. |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ | |