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

Simple item page
dc.creatorShida, Kazuhito
dc.date2007-07-19
dc.date2008-01-12
dc.date.accessioned2026-07-07T08:53:42Z
dc.date.available2026-07-07T08:53:42Z
dc.descriptionA 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.
dc.descriptionAbout 12pages, 1 tables, 4 figures,
dc.identifierhttps://arxiv.org/abs/0707.2853
dc.identifierhttp://arxiv.org/abs/0707.2853
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/145714
dc.subjectStatistical Mechanics
dc.titlePhase transition in the maximum clique problem: the case of Erdos-Renyi graphs
dc.typetext

Files

Collections

arXiv