文献

J-GLOBAL ID：202102226151148182   整理番号：21A3276032

大規模動的ネットワークにおける単一ソース最短経路更新のための並列アルゴリズムテンプレート【JST・京大機械翻訳】

A Parallel Algorithm Template for Updating Single-Source Shortest Paths in Large-Scale Dynamic Networks

著者 (5件)： Khanda Arindam (Department of Computer Science, Missouri University of Science and Technology, Rolla, MO, USA) ,  Srinivasan Sriram (Department of Radiation Oncology, Virginia Commonwealth University, Richmond, VA, USA) ,  Bhowmick Sanjukta (Department of Computer Science and Engineering, University of North Texas, Denton, TX, USA) ,  Norris Boyana (Department of Computer and Information Science, University of Oregon, Eugene, OR, USA) ,  Das Sajal K. (Department of Computer Science, Missouri University of Science and Technology, Rolla, MO, USA)
資料名： IEEE Transactions on Parallel and Distributed Systems  (IEEE Transactions on Parallel and Distributed Systems)
巻： 33  号： 4  ページ： 929-940  発行年： 2022年 
JST資料番号： T0882A  ISSN： 1045-9219  CODEN： ITDSEO  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： アメリカ合衆国 (USA)  言語： 英語 (EN)

抄録/ポイント： 単一ソース最短経路(SSSP)問題は,様々な実用的シナリオで頻繁に発生する古典的グラフ理論問題である。したがって,それを解くために多くの並列アルゴリズムが開発された。しかし,これらのアルゴリズムは静的グラフ上で動作し,一方,多くの実世界問題は動的ネットワークとして最良にモデル化され,ネットワークの構造は時間とともに変化する。従来のSSSPアルゴリズムにおける動的グラフモデリングと仮定された静的グラフモデルの間のこのギャップは,本研究を動機づける。大規模動的ネットワークにおけるSSSPを更新するための新しい並列アルゴリズムフレームワークを提示し,共有メモリとGPUプラットフォームに実装した。基本的なアイデアは,解析に最も関連するネットワークのエッジを格納する根付きツリーデータ構造における情報の変化および更新によって影響を受けるネットワークの一部を同定することである。実世界および合成ネットワークに関する広範な実験的評価は,提案した並列更新アルゴリズムがスケーラブルであり,ほとんどの場合,最先端の再計算-スクラッチアルゴリズムよりも実行時間が有意に少ないことを示した。Copyright 2021 The Institute of Electrical and Electronics Engineers, Inc. All rights reserved. Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： *アルゴリズム ,  グラフ理論 ,  *ネットワーク ,  共有メモリ ,  *並列アルゴリズム
準シソーラス用語： グラフモデル ,  実行時間 ,  *動的ネットワーク ,  ツリーデータ構造 ,  *最短経路 , 【Automatic Indexing@JST】

分類 (4件)： 信号理論  (ND02020G) ,  計算理論  (JB02000A) ,  計算機網  (JC03000K) ,  パターン認識  (JE07000S)

タイトルに関連する用語 (7件)： 大規模 ,  動的ネットワーク ,  ソース ,  最短経路 ,  更新 ,  並列アルゴリズム ,  テンプレート