文献

J-GLOBAL ID：201702238708419286   整理番号：17A0922549

最大独立セット問題のための RS-RSB/簡易-ハード通信を示す厳密アルゴリズム

An Exact Algorithm Exhibiting RS-RSB/Easy-Hard Correspondence for the Maximum Independent Set Problem

著者 (3件)： TAKAHASHI Jun (Univ. Tokyo, Tokyo, JPN) ,  TAKABE Satoshi (Nagoya Inst. Technol., Nagoya, JPN) ,  HUKUSHIMA Koji (Univ. Tokyo, Tokyo, JPN)
資料名： Journal of the Physical Society of Japan  (Journal of the Physical Society of Japan)
巻： 86  号： 7  ページ： 073001.1-073001.4  発行年： 2017年07月15日 
JST資料番号： G0509A  ISSN： 0031-9015  CODEN： JUPSA  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 英語 (EN)

抄録/ポイント： 最大独立セット問題のための最近提案された厳密アルゴリズムを分析した。典型的実行時間は,単純な二進検索と比較して若干のパラメータ領域で指数的に改善された。さらにまた,アルゴリズムは従来の葉除去アルゴリズムが失敗するコア遷移点を克服し,そして,レプリカ対称破壊(RSB)遷移点まで働く。これは,葉除去コア自体がランダム最大独立セット問題で典型的硬さのために十分でないことを示唆し,RSBがアルゴリズム一般のための障害である更なる証拠を提供する。(翻訳著者抄録)

シソーラス用語： 問題 ,  *厳密解 ,  *アルゴリズム ,  時間 ,  パラメータ ,  対称性の破れ

分類 (1件)： 計算機利用技術一般  (JE01000C)

引用文献 (22件)：

• M. Mézard, G. Parisi, and M. Á. Virasoro, Spin Glass Theory and Beyond (World Scientific, Singapore, 1987).
• M. Mézard and A. Montanari, Information, Physics and Computation (Oxford University Press, New York, 2009).
• R. Monasson, R. Zecchina, S. Kirkpatrick, B. Selman, and L. Troyansky, Nature 400, 133 (1999).
• R. Mulet, A. Pagnani, M. Weigt, and R. Zecchina, Phys. Rev. Lett. 89, 268701 (2002).
• M. Weigt and A. K. Hartmann, Phys. Rev. E 63, 056127 (2001).

タイトルに関連する用語 (3件)： 問題 ,  簡易 ,  厳密アルゴリズム