実践におけるより速い完全動的推移閉包【JST・京大機械翻訳】

Hanauer Kathrin; Henzinger Monika; Schulz Christian

プレプリント

J-GLOBAL ID：202202200428778603 整理番号：22P0107472

実践におけるより速い完全動的推移閉包【JST・京大機械翻訳】

Faster Fully Dynamic Transitive Closure in Practice

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

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

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

完全動的遷移閉包問題は,頂点の任意のペア間の有向グラフにおける到達性情報を維持するため,グラフはエッジ挿入と欠失のシーケンスを受ける。問題は,理論で徹底的に調査され,それを解くための多くの特殊化されたアルゴリズムが,ここ10年間提案されている。2つの大規模研究[Frigioni ea,2001;KrommidasおよびZaroliagis,2008]において,多くのこれらのアルゴリズムをグラフトラバースのための単純な静的アルゴリズムに対して実験的に評価し,非常に密なランダムグラフまたは非常に高いクエリ比率を除いて,実際に簡単なアルゴリズムの競争力および優位性を示した。これらの研究の主な欠点は,小さい,そして,ほとんどランダムに生成されたグラフのみを考慮したことである。本論文では,簡単で空間効率の良い全対到達性情報を維持するための新アルゴリズムを設計した。さらに,以前の研究でのそれらよりも数桁大きい,発生および実世界事例の両者について,広範な実験的評価を行った。著者らの結果は,著者らの新しいアルゴリズムが,実際にすべてのタイプの入力に関してすべての最先端のアルゴリズムより優れていることを示した。【JST・京大機械翻訳】

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

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

前のページに戻る