期刊
PHYSICAL REVIEW LETTERS
卷 84, 期 26, 页码 6118-6121出版社
AMERICAN PHYSICAL SOC
DOI: 10.1103/PhysRevLett.84.6118
关键词
-
In this Letter we study the NP-complete vertex cover problem on finite connectivity random graphs. When the allowed size of the cover set is decreased, a discontinuous transition in solvability and typical-case complexity occurs. This transition is characterized by means of exact numerical simulations as well as by analytical replica calculations. The replica symmetric phase diagram is in excellent agreement with numerical findings up to average connectivity e, where replica symmetry becomes locally unstable.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据