抄録/ポイント：
抄録/ポイント
文献の概要を数百字程度の日本語でまとめたものです。
部分表示の続きは、JDreamⅢ(有料)でご覧頂けます。
J-GLOBALでは書誌(タイトル、著者名等)登載から半年以上経過後に表示されますが、医療系文献の場合はMyJ-GLOBALでのログインが必要です。
1999年に,BrodalとFagerberg(BF)は,動的均一スパースグラフの低度配向を維持するためのアルゴリズムを与えた。特に,n-頂点上の動的グラフに対して,すべての時間でαによって有界性を持つ,BFアルゴリズムは,O(logn)不死化更新時間におけるエッジ更新をサポートし,一方,O(α)によって有界のグラフにおける最大外度を維持した。このような方向は,均一スパースグラフのための基本的データ構造を提供し,それは,動的グラフアルゴリズムの過剰に応用を見出した。BFアルゴリズムの顕著な弱点は,エッジ挿入に続く最大外度の一時的ブローアップである。BFは最終的にO(α)にすべての外度を減らすが,いくつかの頂点はプロセスの間にOmega(n)の外度に達する可能性があり,従って,分散システムにおける頂点-重要な品質尺度における局所的記憶利用は有界でない。著者らは,すべての頂点の外部度がすべての時間でO(α)によって有界であることを保証するために,BFアルゴリズムをどのように修正するかを示し,その他の特性の何れかを問わずに,修正アルゴリズムの効率的な分散実装を提示した。これは,頂点における局所メモリ利用が,最大度よりむしろ,高木性(本質的に最も密な部分グラフの平均度である)によって有界である分散ネットワークの最初の表現を提供する。局所メモリ制約がない設定に対して,1つは一時的アウト度ブローアップを極端にし,恒久的アウト度ブローアップを可能にする。これにより,BFアルゴリズムの2番目の顕著な弱点,すなわち本質的に大域的な性質,すなわちエッジ(u,v)の挿入がuとvから任意に遠く離れたエッジの方位の変化を引き起こすかもしれない。筆者らは,頂点に任意の外部結合を保証しない代替局所スキームを提案するが,いくつかの応用に対するBFスキームとしては,ちょうど効率的である。例えば,一様スパースネットワークにおけるサブ対数更新時間による最大マッチングを維持するための局所動的アルゴリズムを得て,この文脈において最先端技術の指数的改善を提供した。Please refer to this article’s citation page on the publisher website for specific rights information. Translated from English into Japanese by JST.【JST・京大機械翻訳】
