抄録/ポイント：
抄録/ポイント
文献の概要を数百字程度の日本語でまとめたものです。
部分表示の続きは、JDreamⅢ(有料)でご覧頂けます。
J-GLOBALでは書誌(タイトル、著者名等)登載から半年以上経過後に表示されますが、医療系文献の場合はMyJ-GLOBALでのログインが必要です。
分布ネットワーク(CONGESTモデル)を用いた全点対最短経路(APSP)を研究した。目標は,通信を利用した各他のノードからの距離を知ること(重み付き)ネットワーク内のすべてのノードである。問題は(1+o(1))-近似O(n)時間アルゴリズム[2],[3],withΩ(n)-時間下界[4]整合した[5],脚注{Θ,O andΩhide多対数因子下限も重み無し場合でもと多項式近似比を持つ重み付きであることに注意すべきである。}を許容する。厳密な計算のための知られてなかったΩ(n)下界またはO(m)上限。本論文では,正確な重み付きAPSPのためのO(n^{5/4})-時間ランダム化(Las Vegas)アルゴリズムを提案したネットワークがスパースではない場合,ナイーブO(m)時間アルゴリズム上の第一の改良を提供する。我々の結果もまた,エッジ重みは非対称}(通信は双方向性であるが指向性症例を別名)事例に対し提示される。各ノードは源からの距離を知りたいという技術もK源最短路}問題のためのO(n^{3/4}k^{1/2}+n)時間アルゴリズムを与える;Elkins最近の結合[6]の場合に=Ω(n^{1/4})を改善した。は古典的スケーリング法の頂部は,分散最短経路計算のための初めての使用であると信じるに分散アルゴリズムを開発することにより,上記の結果を達成した。独立興味があるかもしれない一つの新しいアルゴリズムは逆Rシンク最短路}問題のための,Rシンクの各は他の全てのノードからの距離を知る,各ノードは既に各シンクへの距離を知ることにたいた。はこの問題のためのO(n∪{r})時間アルゴリズムを示した。もう一つの新しいアルゴリズムは短い範囲拡大と呼ばれているが,O(n∪{h})時間で距離に関する知識は追加時間ホップに拡張できることを示した。このために,後に固定できる少量添加}誤差を導入する重量丸めを用いた。Copyright 2017 The Institute of Electrical and Electronics Engineers, Inc. All Rights reserved. Translated from English into Japanese by JST【Powered by NICT】
