文献

J-GLOBAL ID：201802226600955269   整理番号：18A1299197

ビット並列性による全最大クリークの効率的列挙【JST・京大機械翻訳】

Efficiently enumerating all maximal cliques with bit-parallelism

著者 (3件)： San Segundo Pablo (Centre for Automation and Robotics (UPM-CSIC), Jose Gutierrez Abascal 2, Madrid 28006, Spain) ,  Artieda Jorge (Centre for Automation and Robotics (UPM-CSIC), Jose Gutierrez Abascal 2, Madrid 28006, Spain) ,  Strash Darren (Department of Computer Science, Colgate University, Hamilton NY, USA)
資料名： Computers & Operations Research  (Computers & Operations Research)
巻： 92  ページ： 37-46  発行年： 2018年 
JST資料番号： H0216B  ISSN： 0305-0548  CODEN： CMORAP  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： オランダ (NLD)  言語： 英語 (EN)

抄録/ポイント： 最大クリーク計数(MCE)問題には,生物学,化学,社会学,およびグラフモデリングにおける多くの応用がある。この問題は良く研究されているが,多くの現在の研究は,大規模なスパースグラフまたは非常に密なグラフにおける解の発見に焦点を合わせているが,実際にしばしば遭遇するデータ集合を代表する最も困難な中密度ベンチマーク例に対する効率を犠牲にする。著者らは,最大クリーク問題にうまく適用された技術が,これらの事例に関する最先端のMCEアルゴリズムに対する著しい速度利得を与えることを示した。特に,ビット並列性と組み合わせたとき,頂点の固定最大次数一次順序に基づく簡単なgre欲ピボット選択は,Tomoitaらの最先端のアルゴリズムの理論的最悪ケース最適化よりも一貫して優れていることを示した。[理論計算機科学,2006],およびNaude[理論計算機科学,2016]。実験により,著者らのアルゴリズムは,74の標準構造化およびランダムベンチマークインスタンスのうちの60において,Tomitaらの最悪ケース最適アルゴリズムよりも高速であることを示した。48のインスタンスを,1.2から2.2倍速く解き,残りの12のインスタンスを,3.6から47.6倍速く解いた。また,Naudeのアルゴリズムよりも一貫した速度改善を見た。著者らの知る限りでは,これらの標準ベンチマークに関するこれらの最先端のアルゴリズムと比較して,そのようなスピードアップを達成することが最初である。Copyright 2018 Elsevier B.V., Amsterdam. All rights reserved. Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： ベンチマーク ,  最適化 ,  高速度 ,  部分グラフ ,  構造形成 ,  *アルゴリズム ,  利得 ,  社会学
準シソーラス用語： 最適アルゴリズム ,  次数 ,  最先端 ,  最大クリーク問題 ,  *最大クリーク , 【Automatic Indexing@JST】

著者キーワード (5件)： 最大クリーク ,  ビットストリング ,  分枝限定 ,  部分グラフ列挙 ,  組合せ最適化

分類 (2件)： 工程管理  (KB03030P) ,  ネットワーク法  (KA03040X)

タイトルに関連する用語 (2件)： ビット ,  最大クリーク