文献

J-GLOBAL ID：202002264532185747   整理番号：20A1055402

効率的グラフ収縮によるGomory-Hu並列カット木アルゴリズムの高速化【JST・京大機械翻訳】

Speeding Up the Gomory-Hu Parallel Cut Tree Algorithm with Efficient Graph Contractions

著者 (3件)： Maske Charles (Department Informatics, Federal University of Parana, Curitiba, Brazil) ,  Cohen Jaime (Department Informatics, State University of Ponta Grossa, Ponta Grossa, Brazil) ,  Duarte Elias P. Jr. (Department Informatics, Federal University of Parana, Curitiba, Brazil)
資料名： Algorithmica  (Algorithmica)
巻： 82  号： 6  ページ： 1601-1615  発行年： 2020年 
JST資料番号： T0530A  ISSN： 0178-4617  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： ドイツ (DEU)  言語： 英語 (EN)

抄録/ポイント： カットツリーは,非有向グラフのノードのすべてのペア間のエッジ接続性を表す組合せ構造である。カットツリーは,それらがネットワークノードのあらゆるペアを分離するのをいかにしているかを表現するので,信頼性において複数のアプリケーションを持っている。それらは,いくつかの他の応用の間で,連結性問題,経路選定,および複雑なネットワークの解析において使用されてきた。本研究は,古典的なGomey-Huカットツリーアルゴリズムの並列バージョンを提示した。このアルゴリズムは,契約グラフ上の最小カットを計算するタスクに基づいている。主な寄与は,元の入力グラフからすべての収縮を常に計算する代わりに,以前に縮約されたグラフインスタンスの利点を利用することを可能にする,収縮グラフを計算するための効率的な戦略である。提案したアルゴリズムをMPIを用いて実装し,いくつかのグラフに対して実験結果を示し,顕著な性能利得を示した。Copyright Springer Science+Business Media, LLC, part of Springer Nature 2019 Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： *アルゴリズム ,  信頼性 ,  ネットワーク ,  有向グラフ ,  経路選定 ,  応用プログラム ,  利得 ,  高速化 ,  連結性 ,  並列アルゴリズム
準シソーラス用語： ネットワークノード , 【Automatic Indexing@JST】

著者キーワード (4件)： カットツリー ,  並列アルゴリズム ,  Gomory-Huアルゴリズム ,  グラフ収縮

分類 (1件)： グラフ理論基礎  (IA02020S)

タイトルに関連する用語 (6件)： グラフ ,  収縮 ,  HU ,  木 ,  アルゴリズム ,  高速化