多重エッジフォールトトレラント近似最短経路ツリー【JST・京大機械翻訳】

Bilo Davide; Guala Luciano; Leucci Stefano; Proietti Guido; Proietti Guido

文献

J-GLOBAL ID：202202267661288207 整理番号：22A0495865

多重エッジフォールトトレラント近似最短経路ツリー【JST・京大機械翻訳】

Multiple-Edge-Fault-Tolerant Approximate Shortest-Path Trees

出版者サイト複写サービスで全文入手 {{ this.onShowCLink("http://jdream3.com/copy/?sid=JGLOBAL&noSystem=1&documentNoArray=22A0495865&COPY=1") }}
高度な検索・分析はJDreamⅢで {{ this.onShowJLink("http://jdream3.com/lp/jglobal/index.html?docNo=22A0495865&from=J-GLOBAL&jstjournalNo=T0530A") }}

著者 (5件)： , , , ,
資料名：
巻： 84 号： 1 ページ： 37-59 発行年： 2022年
JST資料番号： T0530A ISSN： 0178-4617 資料種別：逐次刊行物 (A)
記事区分：原著論文発行国：ドイツ (DEU) 言語：英語 (EN)

Gをnノードとmエッジ正実重みづけ無向グラフとする。任意の整数[数式:原文を参照]に対して,スパースfエッジフォールトトレラント(f-EFT)[数式:原文を参照]近似単一ソース最短経路ツリー([数式:原文を参照]-ASPT)の設計問題,即ち,できるだけ少ないエッジを持つGのサブグラフ,すなわち,GにおけるほとんどのfエッジのセットFの失敗に続いて,ほとんどの[数式:原文を参照]の因子によって引き伸ばされる固定ソースからの経路を含む。この点に関して,サイズO(fn)のf-EFT[数式:原文を参照]-ASPTを効率的に計算するアルゴリズムを提供した。著者らの構造は,非加重グラフのために設計された以前の関連構造を改善し,同じサイズを持つが,[数式:原文を参照]のより大きな伸張因子,および[数式:原文を参照]の付加的項を保証した。次に,[数式:原文を参照]時間内に構築できる効率的なf-EFT単一ソース距離オラクルに構造をどのように変換するかを示し,サイズ[数式:原文を参照]を持ち,そして,[数式:原文を参照]時間において,[数式:原文を参照]においてソースから任意のノードまでの[数式:原文を参照]近似距離をレポートできる。さらに,著者らのオラクルは,同じ量の時間プラス経路サイズで,対応する近似経路を返すことができる。オラクルは,k同時修正(すなわち,エッジ挿入,欠失および重量変化)のバッチに従って,Gの最小スパニング森林(MSF)を更新するという,別の基本的問題に取り組むことによって得られる。この問題のために,著者らは,[数式:原文を参照]時間において,サイズ[数式:原文を参照]のオラクルを構築し,[数式:原文を参照]時間(ほとんどの2k)のエッジがMSFから出るか,または流入するのを,[数式:原文を参照]時間において報告した。最後に,任意の整数[数式:原文を参照]に対して,[数式:原文を参照]と[数式:原文を参照]を有する任意のf-EFT [数式:原文を参照]-ASPTのサイズに対する[数式:原文を参照]の下限ですべての結果を補完し,もしErdoesのgirth予測が真実であるかどうかを保持した。Copyright The Author(s), under exclusive licence to Springer Science+Business Media, LLC, part of Springer Nature 2021 Translated from English into Japanese by JST.【JST・京大機械翻訳】

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

著者キーワード (3件)： , ,

通信網 , 計算理論 , 数値計算 , ネットワーク法 , グラフ理論基礎

, , , ,

前のページに戻る