文献

J-GLOBAL ID：201002238754132298   整理番号：10A0298490

単純でより高速な最大クリーク抽出アルゴリズム

A Simple and Faster Algorithm for Finding a Maximum Clique

著者 (6件)： TOMITA Etsuji (Univ. Electoro-Communications) ,  TOMITA Etsuji (Chuo Univ.) ,  SUTANI Yoichi (Univ. Electoro-Communications) ,  HIGASHI Takanori (Univ. Electoro-Communications) ,  TAKAHASHI Shinya (Univ. Electoro-Communications) ,  WAKATSUKI Mitsuo (Univ. Electoro-Communications)
資料名： 情報処理学会研究報告(CD-ROM)
巻： 2009  号： 5  ページ： ROMBUNNO.AL-128,NO.10  発行年： 2010年02月15日 
JST資料番号： Z0031C  ISSN： 2186-2583  資料種別： 逐次刊行物 (A)
記事区分： 短報  発行国： 日本 (JPN)  言語： 英語 (EN)

抄録/ポイント： 最大クリーク抽出アルゴリズムMCR(Tomita et al.,J.Global Optim.,37,95-111,2007)は,数多くの問題グラフに対して他よりも非常に高速であることを実験的に確認していた。本稿では,その改良アルゴリズムMCSがMCRや他のアルゴリズムよりも全面的に顕著に高速であることを示す。MCSは特定のグラフに対象を限定したアルゴリズムではないが,枝密度の高い難しいグラフに対しては特により高速である。MCRでは100日以上かかっても解けない幾つかの超高密度ランダムグラフに対し,MCSは数10秒で解を得ることに成功している。(著者抄録)

シソーラス用語： *クリーク ,  *最大化問題 ,  グラフ理論 ,  高速アルゴリズム ,  グラフ ,  性能評価 ,  性能分析 ,  密度
準シソーラス用語： ランダムグラフ ,  *最大クリーク抽出問題 ,  枝【グラフ】 ,  枝密度 ,  超高密度ランダムグラフ

分類 (2件)： グラフ理論基礎  (IA02020S) ,  その他のオペレーションズリサーチの手法  (KA03070E)

タイトルに関連する用語 (2件)： 最大クリーク ,  アルゴリズム