ラベリングースキャニング法による最短経路問題について

• Item type: SIG Technical Reports(1)
• 公開日: 1988-07-25
• タイトル: ラベリングースキャニング法による最短経路問題について
• タイトル / 言語: en
• タイトル: On the shortest path problem wiht labeling - scanning method
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 国際基督教大学理学研究科
• 著者所属: 国際基督教大学理学科
• 著者所属(英): en
• 著者所属(英): International Christian University Division of Natural Science
• 著者所属(英): en
• 著者所属(英): International Christian University Division of Natural Science
• 著者名: 佐藤尚; 野崎, 昭弘
• 著者名(英): Hisashi, Sato; Akihiro, Nozaki
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 辺の長さとして負のものもゆるすグラフの最短経路問題について、FIFO法の計算量の証明を利用して、ラベリング‐スキャンニング法による実行時間O(|V| |E|)とO(|V| |E| log |E|)の新しい方法を考える。そして、これらの新しい方法とFIFO法および両頭列法の比較を、いくつかのグラフを用いておこなう。これらの新しい方法は、複雑なグラフに対して、ある程度有効であることが分かった。
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: For the network optimization problem of finding shortest paths from a source to all the other vertices in a given directed graph whose edges have real-valued lengths, we devise several new methods in labeling and scanning based on a proof of running time of FIFO method. We compare these new methods with the existing FIFO method and a two-way sequence method. These new methods have been found efficient for complex graphs.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 情報処理学会研究報告アルゴリズム（AL）; 巻 1988, 号 56(1988-AL-002), p. 1-7, 発行日 1988-07-25
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会