2007/07/19 by Kazuhito Shida, Shida, Kazuhito
Physics and Astronomy · #FOS: Physical sciences #Statistical Mechanics (cond-mat.stat-mech) #cond-mat.stat-mech
paper · pdf · doi:10.48550/arxiv.0707.2853
About 12pages, 1 tables, 4 figures,
arxiv created 2008/01/12 · arxiv updated 2009/12/01
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.