スライディングウィンドウモデルへの適用による作業効率の良いバッチ増分最小スパンニング木【JST・京大機械翻訳】

Anderson Daniel; Blelloch Guy E.; Tangwongsan Kanat

プレプリント

J-GLOBAL ID：202202213976097902 整理番号：22P0111576

スライディングウィンドウモデルへの適用による作業効率の良いバッチ増分最小スパンニング木【JST・京大機械翻訳】

Work-efficient Batch-incremental Minimum Spanning Trees with Applications to the Sliding Window Model

出版者サイト {{ this.onShowPLink() }} 複写サービスで全文入手
高度な検索・分析はJDreamⅢで

この文献はプレプリントです。プレプリントについてはこちらをご確認ください。

著者 (3件)： , ,
資料名：
発行年： 2020年02月13日プレプリントサーバーでの情報更新日： 2020年02月13日
JST資料番号： O7000B 資料種別：プレプリント
記事区分：プレプリント発行国：アメリカ合衆国 (USA) 言語：英語 (EN)

※このプレプリント論文は学術誌に掲載済みです。なお、学術誌掲載の際には一部内容が変更されている可能性があります。

最小スパニング木(MST)を動的に維持するためのアルゴリズムは,並列および逐次設定の両方で多くの注目を集めている。以前の研究は,高密度グラフのための最適アルゴリズムを与えたが,すべての既存の並列バッチ動的アルゴリズムは,スパースグラフのために最悪ケースにおける更新につき多項式作業を実行した。本論文では,期待およびO(ポリログ(n))スパンw.h.pにおけるO(llog(1+n/l))作業におけるlエッジを挿入できる,増分MSTのための最初の研究効率的並列バッチ動的アルゴリズムを提案した。提案アルゴリズムの鍵成分は,エッジ加重ツリーの圧縮経路ツリーを構築するためのアルゴリズムであり,それは,与えられた顕著な頂点のセットの間に,すべてのペアワイズの重いエッジを含むより小さなツリーである。バッチインクリメンタルMSTアルゴリズムを用いて,グラフ接続性,近似MST,試験二分性,k-証明書,サイクルフリー性,およびスパーサーファイアのようなスライディングウィンドウモデルにおいて並列に効率的に解決できる応用の範囲を示した。【JST・京大機械翻訳】

, , , , , , , , , ,
, , , , 【Automatic Indexing@JST】

計算理論 , グラフ理論基礎

, ,

前のページに戻る