Phase transition in the maximum clique problem: the case of Erdos-Renyi graphs

Thumbnail Image

Date

Authors

Journal Title

Journal ISSN

Volume Title

Publisher

Abstract

Description

A phase transition, like the one already found on Boolean satisfiability problem by Kirkpatrick and Selman, is found on max clique problem on ER graphs. Although number of the datapoints is limited, the transition seems to obey finite size scaling. The transition also shows concentration of the graph instances which need particularly large CPU time to solve.
About 12pages, 1 tables, 4 figures,

Keywords

Statistical Mechanics

Citation

URI

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

Consulte el texto completo en el siguiente enlace:

https://arxiv.org/abs/0707.2853
 http://arxiv.org/abs/0707.2853

Collections

arXiv