| Item type |
SIG Technical Reports(1) |
| 公開日 |
2016-02-28 |
| タイトル |
|
|
タイトル |
最大クリーク抽出アルゴリズムMCSの高速化 |
| タイトル |
|
|
言語 |
en |
|
タイトル |
An Improved MCS Algorithm for Finding a Maximum Clique |
| 言語 |
|
|
言語 |
jpn |
| 資源タイプ |
|
|
資源タイプ識別子 |
http://purl.org/coar/resource_type/c_18gh |
|
資源タイプ |
technical report |
| 著者所属 |
|
|
|
電気通信大学情報理工学部 |
| 著者所属 |
|
|
|
電気通信大学大学院情報理工学研究科 |
| 著者所属 |
|
|
|
電気通信大学先進アルゴリズム研究ステーション |
| 著者所属 |
|
|
|
電気通信大学大学院情報理工学研究科 |
| 著者所属 |
|
|
|
電気通信大学大学院情報理工学研究科 |
| 著者所属 |
|
|
|
電気通信大学大学院情報理工学研究科 |
| 著者名 |
吉田, 幸平
八田, 拓郎
富田, 悦次
長尾, 篤樹
伊藤, 大雄
若月, 光夫
|
| 著者名(英) |
Kohei, Yoshida
Takuro, Hatta
Etsuji, Tomita
Atsuki, Nagao
Hiro, Ito
Mitsuo, Wakatsuki
|
| 論文抄録 |
|
|
内容記述タイプ |
Other |
|
内容記述 |
無向グラフ中の最大クリークを 1 つ抽出する問題は，NP 困難に属する基本的な組合せ最適化問題であり，現実の様々な問題が最大クリーク抽出，あるいはそれに類似した問題としてモデル化できることから，工学的に非常に重要な問題となっている．これに対し，実働上で効率的に解を得ることを目的とした多くのアルゴリズムが開発されてきており，逐次的な近似彩色を用いた分枝限定アルゴリズムが効果的とされている．本稿では，厳密解アルゴリズムの先頭処理として近似解アルゴリズムの適用や，探索節点の順序変更および，部分問題に応じて適用する近似彩色アルゴリズムの適応的な切り替えを主に用いて，従来のアルゴリズム MCS を高速化した．さらに，計算機実験による評価を与えることにより，他のアルゴリズムに対する優位性を示した． |
| 書誌レコードID |
|
|
収録物識別子タイプ |
NCID |
|
収録物識別子 |
AN1009593X |
| 書誌情報 |
研究報告アルゴリズム（AL）
巻 2016-AL-157,
号 8,
p. 1-8,
発行日 2016-02-28
|
| ISSN |
|
|
収録物識別子タイプ |
ISSN |
|
収録物識別子 |
2188-8566 |
| Notice |
|
|
|
SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc. |
| 出版者 |
|
|
言語 |
ja |
|
出版者 |
情報処理学会 |
IPSJ-AL16157008.pdf (681.3 kB)
