講演抄録/キーワード |
講演名 |
2021-03-08 15:45
最大クリーク抽出アルゴリズムMCTのさらなる高速化 ○柳澤士朗・富田悦次(電通大)・片山謙吾・金原一歩(岡山理科大)・戸田貴久・伊藤大雄・若月光夫・西野哲朗(電通大) COMP2020-35 |
抄録 |
(和) |
筆者らが以前に提唱した最大クリーク抽出アルゴリズムMCT (FAW 2016, LNCS 9711, pp.215-226, 2016) の高速化を行った. このために, 最大クリーク抽出の厳密解アルゴリズムの前処理として,最大クリーク近似解抽出アルゴリズムの改良版の導入,効果的な分枝限定を可能にする節点の順序と従来の節点の順序を適切に切り替える処理を導入し,他のアルゴリズムにおいて有効性が確認されている分枝限定法を導入した.
比較実験により, 本提案最大クリーク抽出アルゴリズムは, MCTの着実な高速化に成功していることを確認した. さらに, Chu-Min Liらの提案した最新アルゴリズムIncMC2 (INFORMS J. Computing, 30, pp.137-153, 2018)との比較実験により, 多くの問題についてIncMC2 他のアルゴリズムより高速であることを示した. |
(英) |
We improve further the MCT algorithm for finding a maximum clique (FAW 2016, LNCS 9711, pp.215-226, 2016). First, we employ a new efficient approximation algorithm for finding a maximum clique. Second, we change the threshold to enable the appropriate disposal of search trees depending on the scale. Third, we employ a branch-and-bound technique that has already been shown effective by other algorithms. It is shown that a new algorithm is much faster than MCT by extensive computational experiments. In addition, it is shown that the new algorithm is faster than the up-to-date IncMC2 algorithm (INFORMS J. Computing, 30, pp.137-153, 2018) for many problems. |
キーワード |
(和) |
最大クリーク / 深さ優先探索 / 近似アルゴリズム / グラフ理論 / / / / |
(英) |
maximum clique / depth-first search / approximation algorithm / graph theory / / / / |
文献情報 |
信学技報, vol. 120, no. 426, COMP2020-35, pp. 38-45, 2021年3月. |
資料番号 |
COMP2020-35 |
発行日 |
2021-03-01 (COMP) |
ISSN |
Online edition: ISSN 2432-6380 |
著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
PDFダウンロード |
COMP2020-35 |
|