文献

J-GLOBAL ID：201902225302419974   整理番号：19A1392807

すべての流れに対する最短経路に関する代数理論【JST・京大機械翻訳】

Algebraic theory on shortest paths for all flows

著者 (1件)： Takaoka Tadao (Department of Computer Science, University of Canterbury, Christchurch, New Zealand)
資料名： Theoretical Computer Science  (Theoretical Computer Science)
巻： 774  ページ： 124-132  発行年： 2019年 
JST資料番号： T0022A  ISSN： 0304-3975  CODEN： TCSDIQ  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： オランダ (NLD)  言語： 英語 (EN)

抄録/ポイント： コストと容量でラベル付けされたエッジを持つ有向グラフに対する最短経路問題を考察した。この問題は,すべてのf値に対する最小コストで特定のソースから他のすべての頂点へ流れfを押すことである。t容量値があるならば,著者らは,O(tm+tnlog n)時間におけるすべての容量値のために単一ソース最短経路問題t時間を解明することができて,それはt=mのときO(m2)であった。ここでは,エッジコストがcにより制限された場合,O(cmn)に対してこの時間を改善し,すべての対問題に対して,ある範囲のtとcに対して最良の既知のO(tc1.843n2.843)よりも良好な複雑度O(min{t,cn}n3)をもつ簡単なFloylikeアルゴリズムを与えた。Copyright 2019 Elsevier B.V., Amsterdam. All rights reserved. Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： 最短路問題 ,  アルゴリズム ,  *代数学 ,  有向グラフ
準シソーラス用語： 複雑度 ,  *最短経路 , 【Automatic Indexing@JST】

著者キーワード (4件)： 情報共有 ,  すべての流れに対する最短経路問題 ,  優先順位待ち行列 ,  限られたエッジコスト

分類 (3件)： 図形・画像処理一般  (JE04010I) ,  グラフ理論基礎  (IA02020S) ,  人工知能  (JE08000Z)

タイトルに関連する用語 (4件)： 流れ ,  最短経路 ,  代数 ,  理論