文献

J-GLOBAL ID：201802213444460862   整理番号：18A1789849

最大辺重みクリーク問題に対する局所探索法のためのデータ構造

Data Structures for Local Search Algorithms for the Maximum Edge-weight Clique Problem

著者 (4件)： 清水悟司 (神戸大 大学院工学研究科) ,  石原諒大 (神戸大 大学院工学研究科) ,  山口一章 (神戸大 大学院工学研究科) ,  増田澄男 (神戸大 大学院工学研究科)
資料名： 情報処理学会論文誌ジャーナル(Web)
巻： 59  号： 7  ページ： 1415-1424 (WEB ONLY)  発行年： 2018年07月15日 
JST資料番号： U0452A  ISSN： 1882-7764  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 日本語 (JA)

抄録/ポイント： 辺に重みが付与された無向グラフが与えられたとき,重みの和が最大となるクリークを求める問題を最大辺重みクリーク問題という。本稿ではこの問題に対する局所探索法において近傍を管理するためのデータ構造を2つ提案する。計算機実験により2つの局所探索法でデータ構造を比較し,提案法は従来法より性能が良いことを確認した。また,グラフの性質や計算機のメモリに応じて提案するデータ構造を使い分けることで,効率良く探索を行えることを確認した。(著者抄録)

シソーラス用語： *最大化問題 ,  *クリーク ,  *近傍探索法 ,  データ構造 ,  計算機シミュレーション ,  NP困難 ,  計算機利用 ,  利用
準シソーラス用語： *最大クリーク問題 ,  *最大辺重みクリーク問題 ,  *局所探索法 ,  計算機実験

分類 (1件)： 計算理論  (JB02000A)

引用文献 (23件)：

• Gary, M.R. and Johnson, D.S.: Computers and Intractability - A Guide to the Theory of NPcompleteness, W H Freeman and Company (1979).
• Bogdanova, G.T., Brouwer, A.E., Kapralov, S.N. and Östergård, P.R.: Error-correcting codes over an alphabet of four elements, Designs, Codes and Cryptography, Vol.23, No.3, pp.333-342 (2001).
• Sorour, S. and Valaee, S.: Minimum broadcast decoding delay for generalized instantly decodable network coding, Global Telecommunications Conference, pp.1-5, IEEE (2010).
• Horaud, R. and Skordas, T.: Stereo correspondence through feature grouping and maximal cliques, IEEE Trans. Pattern Analysis and Machine Intelligence, Vol.11, No.11, pp.1168-1180 (1989).
• KC, D.B., Akutsu, T., Tomita, E., Seki, T. and Fujiyama, A.: Point matching under non-uniform distortions and protein side chain packing based on efficient maximum clique algorithms, Genome Informatics, Vol.13, pp.143-152 (2002).

タイトルに関連する用語 (4件)： 辺 ,  クリーク ,  局所探索法 ,  データ構造