文献

J-GLOBAL ID：201702286028084687   整理番号：17A0371451

初期併合と分割戦略による効率的なk端連結成分検出【Powered by NICT】

Efficient k-edge connected component detection through an early merging and splitting strategy

著者 (7件)： Sun Heli (Department of Computer Science and Technology, Xi’an Jiaotong University, Xi’an, 710049, China) ,  Huang Jianbin (School of Software, Xidian University, Xi’an, 710071, China) ,  Bai Yang (School of Software, Xidian University, Xi’an, 710071, China) ,  Zhao Zhongmeng (Department of Computer Science and Technology, Xi’an Jiaotong University, Xi’an, 710049, China) ,  Jia Xiaolin (Department of Computer Science and Technology, Xi’an Jiaotong University, Xi’an, 710049, China) ,  He Fang (Department of Computer Science and Technology, Xi’an Jiaotong University, Xi’an, 710049, China) ,  Li Yang (Department of Computer Science and Technology, Xi’an Jiaotong University, Xi’an, 710049, China)
資料名： Knowledge-Based Systems  (Knowledge-Based Systems)
巻： 111  ページ： 63-72  発行年： 2016年 
JST資料番号： T0426A  ISSN： 0950-7051  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： オランダ (NLD)  言語： 英語 (EN)

抄録/ポイント： 計算k端連結成分グラフにおける密接に関連した頂点を捕らえるために使用できる。は多くの用途を持つ重要な問題である。k端連結成分を計算するための伝統的なアルゴリズムの高時間複雑さのために,大規模グラフを効率的に処理に利用することが困難である。本論文では,MSKと命名した初期融合と分裂に基づく最大k-エッジ連結部分グラフ検出アルゴリズムを提案した。グラフの頂点の連結性に従って決定した頂点の順序リストを用いたグラフのk端連結成分を計算する。頂点リストの加工中に,二頂点がk端を接続されているならば,それらは超バーテックスに併合する。一方,頂点対はk辺連結性の条件を満たさない場合,関連した頂点と辺をグラフから除去され,グラフはいくつかの部分グラフに分解した。各部分グラフがk-エッジ連結成分になるまで上記ステップは得られた部分グラフにおける反復的に行った。時間効率をさらに改善するために,近似アルゴリズムPMSKも提案した。多数実および人工的グラフの上での実験結果により,提案したアルゴリズムは正確であり,最先端のアルゴリズムよりもより効率的であることを示した。Copyright 2017 Elsevier B.V., Amsterdam. All rights reserved. Translated from English into Japanese by JST.【Powered by NICT】

シソーラス用語： *部分グラフ ,  アルゴリズム ,  連結性 ,  輪郭近似
準シソーラス用語： 近似アルゴリズム ,  検出アルゴリズム ,  *連結成分 , 【Automatic Indexing@JST】

著者キーワード (4件)： グラフ分解 ,  Subgraph ,  k-辺連結性 ,  グラフマイニング

分類 (2件)： 人工知能  (JE08000Z) ,  グラフ理論基礎  (IA02020S)

タイトルに関連する用語 (4件)： 初期 ,  併合 ,  戦略 ,  連結成分