WEKO3
アイテム
単純でより高速な最大クリーク抽出アルゴリズム
https://ipsj.ixsq.nii.ac.jp/records/67309
https://ipsj.ixsq.nii.ac.jp/records/6730987970de7-3ec4-4638-93f9-6d901039434b
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
IPSJ-AL10128010.pdf (201.6 kB)
|
Copyright (c) 2010 by the Information Processing Society of Japan
|
|
| オープンアクセス | ||
| Item type | SIG Technical Reports(1) | |||||||
|---|---|---|---|---|---|---|---|---|
| 公開日 | 2010-01-19 | |||||||
| タイトル | ||||||||
| タイトル | 単純でより高速な最大クリーク抽出アルゴリズム | |||||||
| タイトル | ||||||||
| 言語 | en | |||||||
| タイトル | A Simple and Faster Algorithm for Finding a Maximum Clique | |||||||
| 言語 | ||||||||
| 言語 | eng | |||||||
| 資源タイプ | ||||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_18gh | |||||||
| 資源タイプ | technical report | |||||||
| 著者所属 | ||||||||
| 電気通信大学／中央大学研究開発機構 | ||||||||
| 著者所属 | ||||||||
| 電気通信大学 | ||||||||
| 著者所属 | ||||||||
| 電気通信大学 | ||||||||
| 著者所属 | ||||||||
| 電気通信大学 | ||||||||
| 著者所属 | ||||||||
| 電気通信大学 | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| The University of Electro-Communications / Research and Development Initiative, Chuo University | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| The University of Electro-Communications | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| The University of Electro-Communications | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| The University of Electro-Communications | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| The University of Electro-Communications | ||||||||
| 著者名 |
富田, 悦次
× 富田, 悦次
|
|||||||
| 著者名(英) |
Etsuji, Tomita
× Etsuji, Tomita
|
|||||||
| 論文抄録 | ||||||||
| 内容記述タイプ | Other | |||||||
| 内容記述 | 最大クリーク抽出アルゴリズム MCR (Tomita et al., J. Global Optim., 37, 95-111, 2007) は，数多くの問題グラフに対して他よりも非常に高速であることを実験的に確認していた. 本稿では，その改良アルゴリズム MCS が MCR や他のアルゴリズムよりも全面的に顕著に高速であることを示す．MCS は特定のグラフに対象を限定したアルゴリズムではないが，枝密度の高い難しいグラフに対しては特により高速である．MCR では 100 日以上かかっても解けない幾つかの超高密度ランダムグラフに対し，MCS は数 10 秒で解を得ることに成功している． | |||||||
| 論文抄録(英) | ||||||||
| 内容記述タイプ | Other | |||||||
| 内容記述 | A maximum-clique-finding algorithm MCR (Tomita et al., J. Global Optim., 37, 95-111, 2007) was the fastest among all the existing algorithms in computational experiments for a large number of tested graphs. In this note, it is shown by extensive computational experiments that MCS is remarkably faster than MCR and other algorithms. In particular, it is very much faster than MCR for difficult graphs of very high density, even though MCS is not designed for any particular type of graphs. MCS can find a maximum clique in less than 100 seconds for some extremely dense random graphs while MCR requires more than 100 days for the same graphs. | |||||||
| 書誌レコードID | ||||||||
| 収録物識別子タイプ | NCID | |||||||
| 収録物識別子 | AN1009593X | |||||||
| 書誌情報 |
研究報告アルゴリズム（AL） 巻 2010-AL-128, 号 10, p. 1-4, 発行日 2010-01-19 |
|||||||
| Notice | ||||||||
| SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc. | ||||||||
| 出版者 | ||||||||
| 言語 | ja | |||||||
| 出版者 | 情報処理学会 | |||||||
