文献

J-GLOBAL ID：202002217173632931   整理番号：20A1867560

ほぼ線形の仕事と低い深さにおける並列最小カット【JST・京大機械翻訳】

Parallel Minimum Cuts in Near-linear Work and Low Depth

著者 (2件)： Geissmann Barbara (ETH Zuerich, Zuerich, Switzerland) ,  Gianinazzi Lukas (ETH Zuerich, Zuerich, Switzerland)
資料名： ACM Proceedings  (ACM Proceedings)
号： SPAA ’18  ページ： 1-11  発行年： 2018年 
JST資料番号： D0698C  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： アメリカ合衆国 (USA)  言語： 英語 (EN)

抄録/ポイント： 著者らは,グラフにおける最小カットを計算するための最初の近線形研究および多対数深度アルゴリズムを提示し,一方,頂点数における少なくとも二次作業に必要な多対数深度を有する以前の並列アルゴリズムを示した。n頂点とmエッジを有するグラフにおいて,著者らのアルゴリズムは,O(mlog4n)作業とO(log3n)深さにおける高い確率で正しい結果を計算する。この結果は,木の経路に沿って重みを集約し,最小カットとスパンニング木の近似最大充填の間の接続を利用することによって,データ構造を並列化することによって得られる。さらに,このアルゴリズムは,最小カットを計算するのに必要なキャッシュミスの数に関する限界を改善した。Please refer to this article’s citation page on the publisher website for specific rights information. Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： *アルゴリズム ,  データ構造 ,  近似法 ,  キャッシュメモリ ,  線形性 ,  対数 ,  スパンニング木 ,  並列アルゴリズム
準シソーラス用語： グラフアルゴリズム ,  キャッシュミス , 【Automatic Indexing@JST】

著者キーワード (5件)： キャッシュ忘却アルゴリズム ,  グラフアルゴリズム ,  最小カット ,  最小経路データ構造 ,  並列アルゴリズム

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

タイトルに関連する用語 (2件)： 線形 ,  仕事