講演抄録/キーワード |
講演名 |
2018-10-26 11:15
近似最大クリーク抽出アルゴリズムIKLSの反復回数に対する適切な制御方法 ○長尾篤樹(お茶の水女子大)・松崎空良・富田悦次・伊藤大雄・若月光夫・西野哲朗(電通大) COMP2018-23 |
抄録 |
(和) |
筆者らが以前に提唱した最大クリーク抽出アルゴリズム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. |
キーワード |
(和) |
最大クリーク抽出問題 / ヒューリスティック / 近似アルゴリズム / グラフ理論 / / / / |
(英) |
/ / / / / / / |
文献情報 |
信学技報, vol. 118, no. 268, COMP2018-23, pp. 17-24, 2018年10月. |
資料番号 |
COMP2018-23 |
発行日 |
2018-10-19 (COMP) |
ISSN |
Online edition: ISSN 2432-6380 |
著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
PDFダウンロード |
COMP2018-23 |