文献

J-GLOBAL ID：201802228418021012   整理番号：18A0276585

大規模疎グラフにおける最大クリーク数え上げのための線形時間アルゴリズム【Powered by NICT】

A linear time algorithm for maximal clique enumeration in large sparse graphs

著者 (2件)： Yu Ting (State Key Lab of Software Engineering, Wuhan University, Hubei, PR China) ,  Liu Mengchi (State Key Lab of Software Engineering, Wuhan University, Hubei, PR China)
資料名： Information Processing Letters  (Information Processing Letters)
巻： 125  ページ： 35-40  発行年： 2017年 
JST資料番号： E0513A  ISSN： 0020-0190  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： オランダ (NLD)  言語： 英語 (EN)

抄録/ポイント： 最大クリークは無向グラフにおける最も基本的な密な構造の一つであり,最大クリーク列挙(MCE)は密に接続された部分グラフ発見において重要な役割を果たしている。最大クリーク数え上げの既存のアルゴリズムは,思考導波,高時間複雑性を招くとして隣接ノードの再帰反復法を採用した。本論文では,結果として候補マップと呼ばれる新しいデータ構造を生成する大規模スパースグラフにおける最大クリーク数え上げのための,CM構成子(候補地図構成),線形時間アルゴリズムを提案した。候補マップは無向グラフのすべての最大クリーク,逆クリークツリーを介して廃棄され容易にできることをいくつかの非最大クリークを保持している。著者らの知る限り,CM構成素線形手法を用いた最大クリーク列挙問題を捕捉するための最初のアルゴリズムである。O(| E |)時間内で無向グラフG=(V , E)の重複なしに全ての極大クリークを生成する。Copyright 2018 Elsevier B.V., Amsterdam. All rights reserved. Translated from English into Japanese by JST.【Powered by NICT】

シソーラス用語： *アルゴリズム ,  *線形性 ,  部分グラフ ,  計算量 ,  データ構造 ,  逐次近似 ,  無向グラフ ,  *グラフ
準シソーラス用語： 複雑性 ,  *線形時間アルゴリズム ,  *最大クリーク , 【Automatic Indexing@JST】

著者キーワード (5件)： グラフアルゴリズム ,  最大クリーク数え上げ ,  データ構造 ,  計算の複雑さ ,  線形時間アルゴリズム

分類 (2件)： 計算理論  (JB02000A) ,  グラフ理論基礎  (IA02020S)

タイトルに関連する用語 (4件)： 大規模 ,  グラフ ,  最大クリーク ,  線形時間アルゴリズム