文献

J-GLOBAL ID：202102260657043264   整理番号：21A0568666

頂点移動ペナルティを持つネットワークにおける最短経路発見のためのアルゴリズム【JST・京大機械翻訳】

Algorithms for Finding Shortest Paths in Networks with Vertex Transfer Penalties

著者 (1件)： Lewis Rhyd (School of Mathematics, Cardiff University, Cardiff CF10 3AT, Wales, UK)
資料名： Algorithms (Web)  (Algorithms (Web))
巻： 13  号： 11  ページ： 269  発行年： 2020年 
JST資料番号： U7130A  ISSN： 1999-4893  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： スイス (CHE)  言語： 英語 (EN)

抄録/ポイント： 本論文では,エッジ加重グラフにおける最短経路問題を解くためのよく知られたアルゴリズムの多くをレビューした。次に,付加的なペナルティが頂点で引き起こされるこの問題の変種に焦点を当てた。これらのペナルティは,公共輸送における移動による道路接合部と遅延における待ち時間のような物をモデル化するのに使用できる。このようなペナルティを扱う通常の方法はグラフ拡張を通している。代替として,元の非拡張グラフ上で動作するDijkstrasアルゴリズムの2つの変形を提案した。次に,これらの方法の相対的利点と短所を測定するために,解析を提示した。漸近的に,拡張グラフ上のDijkstrasアルゴリズムと比較して,著者らの最初の変異体は,非常に疎なグラフでより速く,しかし,高密度グラフで遅くなった。対照的に,第2のバリアントは,同じ最悪ケース実行時間であった。Copyright 2021 The Author(s) All rights reserved. Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： *アルゴリズム ,  最短路問題 ,  *ネットワーク ,  道路 ,  接合部 ,  公共輸送 ,  待ち時間 ,  *ペナルティ
準シソーラス用語： 実行時間 ,  Dijkstraアルゴリズム ,  高密度 ,  *最短経路 , 【Automatic Indexing@JST】

著者キーワード (4件)： 最短経路問題 ,  Dijkstraアルゴリズム ,  輸送ペナルティ ,  公共輸送

分類 (2件)： グラフ理論基礎  (IA02020S) ,  計算理論  (JB02000A)

引用文献 (32件)：

• Mills, B. Theoretical Introduction to Programming; Springer: London, UK, 2005.
• Six Degrees of Separation. 2020. Available online: https://en.wikipedia.org/wiki/Six_degrees_of_separation (accessed on 19 July 2020).
• Lewis, R. Who is the Centre of the Movie Universe? Using Python and NetworkX to Analyse the Social Network of Movie Stars. arXiv 2020, arXiv:2002.11103.
• Sedgewick, R. Algorithms in Java, Part 5: Graph Algorithms, 3rd ed.; AddisonWesley Professional: Boston, MA, USA, 2003.
• Cormen, T.; Leiserson, C.; Rivest, R.; Stein, C. Introduction to Algorithms, 3rd ed.; The MIT Press: Cambridge, MA, USA, 2009.

タイトルに関連する用語 (3件)： ペナルティ ,  経路発見 ,  アルゴリズム