| 講演名 | 2018-10-26 近似最大クリーク抽出アルゴリズムIKLSの反復回数に対する適切な制御方法 長尾 篤樹(お茶の水女子大), 松崎 空良(電通大), 富田 悦次(電通大), 伊藤 大雄(電通大), 若月 光夫(電通大), 西野 哲朗(電通大), |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | 筆者らが以前に提唱した最大クリーク抽出アルゴリズムMCT (FAW 2016, LNCS 9711, pp.215-226, 2016) に対し，前処理として近似最大クリーク抽出アルゴリズムIKLSを取り込む事で更なる高速化を行った．IKLSは反復を含むアルゴリズムであり，本稿ではIKLSを取り込むにあたって適切な反復回数を制御するアルゴリズムを提案する．さらに，このアルゴリズムと効果的な分枝限定を可能にする節点の順序と従来の節点の順序を適切に切り替える処理を導入することで実現される．本稿で提唱する最大クリーク抽出アルゴリズムは Chu-Min Liらの提案した最新アルゴリズムIncMC2 （INFORMS J. Computing, 30, pp.137-153, 2018）との比較実験により, 多くの問題についてIncMC2 他のアルゴリズムより高速であることを示した. |
| 抄録(英) | We enhance MCT (an algorithm for the maximum clique problem; presented by authors in FAW 2016, LNCS 9711, pp.215-226, 2016) using modified IKLS: a heuristic algorithm for the maximum clique problem. Since IKLS contains some repetition in itself, we need to control algorithm., We present a new algorithm for the maximum clique problem using the above algorithm and a procedure for switching ways of ordering the vertices and show our new algorithm is faster than IncMC2 (an algorithm presented by Chu-Min Li and et. al. in INFORMS J. Computing, 30, pp.137-153, 2018) on most of the benchmark problems and problems on random graphs. |
| キーワード(和) | 最大クリーク抽出問題 / ヒューリスティック / 近似アルゴリズム / グラフ理論 |
| キーワード(英) | |
| 資料番号 | COMP2018-23 |
| 発行日 | 2018-10-19 (COMP) |
| 研究会情報 | |
| 研究会 | COMP |
|---|---|
| 開催期間 | 2018/10/26(から1日開催) |
| 開催地（和） | 京都大学 |
| 開催地（英） | Kyoto University |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | 藤戸 敏弘(豊橋技科大) |
| 委員長氏名（英） | Toshihiro Fujito(Toyohashi Univ. of Tech.) |
| 副委員長氏名（和） | 中野 眞一(群馬大) |
| 副委員長氏名（英） | Shinichi Nakano(Gunma Univ.) |
| 幹事氏名（和） | 玉置 卓(京大) / 大舘 陽太(熊本大) |
| 幹事氏名（英） | Suguru Tamaki(Kyoto Univ.) / Yota Otachi(Kumamoto Univ) |
| 幹事補佐氏名（和） | 脊戸 和寿(成蹊大) |
| 幹事補佐氏名（英） | Kazuhisa Seto(Seikei Univ.) |
| 講演論文情報詳細 | |
| 申込み研究会 | Technical Committee on Theoretical Foundations of Computing |
|---|---|
| 本文の言語 | JPN-ONLY |
| タイトル（和） | 近似最大クリーク抽出アルゴリズムIKLSの反復回数に対する適切な制御方法 |
| サブタイトル（和） | |
| タイトル（英） | |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 最大クリーク抽出問題 |
| キーワード(2)（和/英） | ヒューリスティック |
| キーワード(3)（和/英） | 近似アルゴリズム |
| キーワード(4)（和/英） | グラフ理論 |
| 第 1 著者 氏名（和/英） | 長尾 篤樹 / Atsuki Nagao |
| 第 1 著者 所属（和/英） | お茶の水女子大学(略称：お茶の水女子大) Ochanomizu University(略称：Ochanomizu Univ.) |
| 第 2 著者 氏名（和/英） | 松崎 空良 / Sora Matsuzaki |
| 第 2 著者 所属（和/英） | 電気通信大学(略称：電通大) The university of Electro-communications(略称：UEC) |
| 第 3 著者 氏名（和/英） | 富田 悦次 / Etsuji Tomita |
| 第 3 著者 所属（和/英） | 電気通信大学(略称：電通大) The university of Electro-communications(略称：UEC) |
| 第 4 著者 氏名（和/英） | 伊藤 大雄 / Hiro Ito |
| 第 4 著者 所属（和/英） | 電気通信大学(略称：電通大) The university of Electro-communications(略称：UEC) |
| 第 5 著者 氏名（和/英） | 若月 光夫 / Mitsuo Wakatsuki |
| 第 5 著者 所属（和/英） | 電気通信大学(略称：電通大) The university of Electro-communications(略称：UEC) |
| 第 6 著者 氏名（和/英） | 西野 哲朗 / Tetsuro Nishino |
| 第 6 著者 所属（和/英） | 電気通信大学(略称：電通大) The university of Electro-communications(略称：UEC) |
| 発表年月日 | 2018-10-26 |
| 資料番号 | COMP2018-23 |
| 巻番号（vol） | vol.118 |
| 号番号（no） | COMP-268 |
| ページ範囲 | pp.17-24(COMP), |
| ページ数 | 8 |
| 発行日 | 2018-10-19 (COMP) |