发帖
雷达卡
摘要翻译：
与Kirkpatrick和Selman在布尔可满足性问题上已发现的相变一样，在ER图的极大团问题上也发现了相变。尽管datapoints的数量是有限的，但转换似乎服从有限的大小缩放。转换还显示了图实例的集中，这些图实例需要特别大的CPU时间来解决。
---
英文标题：
《Phase transition in the maximum clique problem: the case of Erdos-Renyi
graphs》
---
作者：
Kazuhito Shida
---
最新提交年份：
2008
---
分类信息：
一级分类：Physics 物理学
二级分类：Statistical Mechanics 统计力学
分类描述：Phase transitions, thermodynamics, field theory, non-equilibrium phenomena, renormalization group and scaling, integrable models, turbulence
相变，热力学，场论，非平衡现象，重整化群和标度，可积模型，湍流
--
---
英文摘要：
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.
---
PDF链接：
https://arxiv.org/pdf/707.2853
京公网安备 11010802022788号
