WEKO3
アイテム
NII Technical Report (NII-2008-004E)：Levelwise Mesh Sparsification for Shortest Path Queries
https://doi.org/10.20736/0000001242
https://doi.org/10.20736/0000001242658953ba-005e-4ead-87dc-b9dd52031de2
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
NII Technical Report (NII-2008-004E)：Levelwise Mesh Sparsification for Shortest Path Queries (383.4 kB)
|
|
| アイテムタイプ | レポート / Report(1) | |||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 公開日 | 2019-03-12 | |||||||||||||||||
| タイトル | ||||||||||||||||||
| タイトル | NII Technical Report (NII-2008-004E)：Levelwise Mesh Sparsification for Shortest Path Queries | |||||||||||||||||
| 言語 | en | |||||||||||||||||
| 言語 | ||||||||||||||||||
| 言語 | eng | |||||||||||||||||
| キーワード | ||||||||||||||||||
| 言語 | ja | |||||||||||||||||
| 主題Scheme | Other | |||||||||||||||||
| 主題 | テクニカルレポート | |||||||||||||||||
| キーワード | ||||||||||||||||||
| 言語 | en | |||||||||||||||||
| 主題Scheme | Other | |||||||||||||||||
| 主題 | Technical Report | |||||||||||||||||
| 資源タイプ | ||||||||||||||||||
| 資源 | http://purl.org/coar/resource_type/c_6501 | |||||||||||||||||
| タイプ | departmental bulletin paper | |||||||||||||||||
| ID登録 | ||||||||||||||||||
| ID登録 | 10.20736/0000001242 | |||||||||||||||||
| ID登録タイプ | JaLC | |||||||||||||||||
| 著者 |
宮本, 裕一郎
× 宮本, 裕一郎
× 宇野, 毅明
× 久保, 幹雄
|
|||||||||||||||||
| 抄録 | ||||||||||||||||||
| 内容記述タイプ | Abstract | |||||||||||||||||
| 内容記述 | The shortest path problem is one of the most fundamental problems in computer science. Although several quasi linear time algorithms have been proposed, even an optimal algorithm does not terminate in sufficiently short time for large-scale networks, such as web networks and road networks. An approach to solving this problem is to construct data structures that enable us to find solutions in a short time. This approach is efficient for applications in which the networks are fixed and we have to answer possibly many questions in a short time, such as in car navigation systems. In this paper, we propose the levelwise mesh sparsification method for the problem. Several sparse networks are obtained by sparsifying the original network, and the shortest path problem is solved by finding the shortest path in these networks. The obtained networks are sparse and small, thus the computational time is short. Computational experiments on real world data show the efficiency of our method in terms of computational time and memory efficiency. Compared with existing approaches, the advantage of our method is that it can deal with negative costs and time-dependent costs, and uses only a small amount of memory. | |||||||||||||||||
| 言語 | en | |||||||||||||||||
| 書誌情報 |
ja : NIIテクニカル・レポート en : NII Technical Report p. 1-9, 発行日 2008-03-31 |
|||||||||||||||||
| 出版者 | ||||||||||||||||||
| 出版者 | 国立情報学研究所 | |||||||||||||||||
| 言語 | ja | |||||||||||||||||
| ISSN | ||||||||||||||||||
| 収録物識別子タイプ | ISSN | |||||||||||||||||
| 収録物識別子 | 1346-5597 | |||||||||||||||||
