抄録/ポイント：
抄録/ポイント
文献の概要を数百字程度の日本語でまとめたものです。
部分表示の続きは、JDreamⅢ(有料)でご覧頂けます。
J-GLOBALでは書誌(タイトル、著者名等)登載から半年以上経過後に表示されますが、医療系文献の場合はMyJ-GLOBALでのログインが必要です。
深さ第一探索(DFS)ツリーは様々なグラフ問題を解くための基本的なデータ構造である。DFSツリーを構築するための古典的アルゴリズム[54]は,n頂点とmエッジを持つ与えられた無有向グラフGに対してO(m+n)時間を必要とする。最近,Baswanaら[5]は,O(n)~1時間におけるエッジ/頂点更新の後,有向グラフのDFSツリーを更新するための簡単なアルゴリズムを提示した。しかしながら,それらのアルゴリズムは厳密に連続している。並列環境に容易に適用できる類似の限界を達成するアルゴリズムを示した。並列環境において,DFSツリーはEREW PRAM上で期待されるO(1)時間[2]におけるスクラッチから計算できるが,最良の決定論的アルゴリズムはCRCW PRAM上でO(√n)時間[2,27]を取る。著者らのアルゴリズムは,完全に動的なDFSを維持するための最適時間(ポリlog n因子)決定論的並列アルゴリズムと,無有向グラフグラフの故障耐性DFSを開発するために使用することができる。(1)並列完全動的DFS:頂点またはエッジ更新の任意のオンラインシーケンスを与えて,著者らは,EREW PRAM上のmプロセッサを用いて,O(1)時間における非有向グラフのDFSツリーを維持することができた。(2)並列故障耐性DFS::無有向グラフグラフを,サイズO(m)のデータ構造を構築するために前処理することができる。例えば,グラフにおける任意のk更新(kは定数)のために,更新グラフのDFSツリーは,EREW PRAM上のnプロセッサを用いてO(1)時間で計算できる。一定kに対しても,これは最適(ポリlog n因子に対して)である。さらに,完全に動的なDFSアルゴリズムは,半ストリーミング環境と制限された分散モデルにおけるDFSツリーを維持するために,シームレスな方法で,ほとんど最適な(ポリlog n因子)アルゴリズムを提供する。これらは,動的設定におけるDFSツリーを維持するための最初の並列,半ストリーミング,および分散アルゴリズムである。Please refer to this article’s citation page on the publisher website for specific rights information. Translated from English into Japanese by JST.【JST・京大機械翻訳】
