抄録/ポイント：
抄録/ポイント
文献の概要を数百字程度の日本語でまとめたものです。
部分表示の続きは、JDreamⅢ(有料)でご覧頂けます。
J-GLOBALでは書誌(タイトル、著者名等)登載から半年以上経過後に表示されますが、医療系文献の場合はMyJ-GLOBALでのログインが必要です。
本稿では,負の長さのエッジを持つ伝統的ネットワーク内の頂点からの最短路を求めるための3つのO(n
0S(m,n))アルゴリズムを提案した。ここで,S(m,n)は,mエッジ/n頂点の有向グラフに関するDijkstra手法の複雑さであり,n
0は負の長さのエッジに付随する頂点の数である。本研究は,S.Fujishigeの手法に動機付けられたものであり,同手法の実行時間は筆者等による提案手法と同等である。同氏は,与えられたlength関数が減少する場合に関して,頂点集合内のすべての頂点から与えられた頂点集合内のすべての頂点への最短路を更新している。これは,筆者等のものとは若干異なる問題である。同氏の貢献は,S.GotoおよびA.Sangiovanni-Vincentelliによって以前に提案されたアルゴリズムよりも少ない初期データを用いた単純なDijkstraアルゴリズムを適用して問題を解いたことにある。Fujishigeは,頂点vからの最短路を計算する部分問題を導入すると共に,負のエッジは頂点vに付随するエッジのみに制限している。そして,各頂点ペア間の最短路の長さを事前情報として仮定した場合,その問題は一連の部分問題にDijkstra手法を連続的に適用することによって解けることを指摘した。筆者等のアプローチはFujishigeのものよりも汎用的である。実際,我々のアプローチは,最短路の更新のみに限定されないほか,そのような事前情報も要求しない。筆者等の各アルゴリズムも同氏が採用した縮小length関数の概念を利用している。さらに筆者等は,提案アルゴリズムに付加的なルーチンを組み込んだ場合,それらのアルゴリズムは特定クラスのインスタンスに対してDijkstra手法を最大でもn
0/2回だけしか適用しないことを示した。それらのインスタンスの部分グラフは,負のエッジに起因する非有向フォレストである。(翻訳著者抄録)
