WEKO3
アイテム
Constant-work-space algorithms for shortest paths in trees and simple polygons
https://doi.org/10.24517/00062800
https://doi.org/10.24517/000628001e688c62-8c97-42b9-8548-ca7ec917729e
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
TE-PR-ASANO-T-569.pdf (1.6 MB)
|
.png)
|
| アイテムタイプ | 学術雑誌論文 / Journal Article(1) | |||||||
|---|---|---|---|---|---|---|---|---|
| 公開日 | 2021-07-05 | |||||||
| タイトル | ||||||||
| タイトル | Constant-work-space algorithms for shortest paths in trees and simple polygons | |||||||
| 言語 | ||||||||
| 言語 | eng | |||||||
| 資源タイプ | ||||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_6501 | |||||||
| 資源タイプ | journal article | |||||||
| ID登録 | ||||||||
| ID登録 | 10.24517/00062800 | |||||||
| ID登録タイプ | JaLC | |||||||
| 著者 |
Asano, Tetsuo
× Asano, Tetsuo× Mulzer, Wolfgang× Wang, Yajun |
|||||||
| 著者別表示 |
浅野, 哲夫
× 浅野, 哲夫
|
|||||||
| 提供者所属 | ||||||||
| 内容記述タイプ | Other | |||||||
| 内容記述 | 金沢大学 | |||||||
| 書誌情報 |
Journal of Graph Algorithms and Applications 巻 15, 号 5, p. 569-586, 発行日 2011 |
|||||||
| ISSN | ||||||||
| 収録物識別子タイプ | ISSN | |||||||
| 収録物識別子 | 1526-1719 | |||||||
| DOI | ||||||||
| 関連タイプ | isIdenticalTo | |||||||
| 識別子タイプ | DOI | |||||||
| 関連識別子 | 10.7155/jgaa.00240 | |||||||
| 出版者 | ||||||||
| 出版者 | Brown University | |||||||
| 抄録 | ||||||||
| 内容記述タイプ | Abstract | |||||||
| 内容記述 | Constant-work-space algorithms model computation when space is at a premium: the input is given as a read-only array that allows random ac- cess to its entries, and the algorithm may use constantly many additional registers of O(logn) bits each, where n denotes the input size. We present such algorithms for two restricted variants of the shortest path problem. First, we describe how to report a simple path between two arbitrary nodes in a given tree. Using a technique called "computing instead of storing", we obtain a naive algorithm that needs quadratic time and a constant number of additional registers. We then show how to improve the running time to linear by applying a technique named "simulated parallelization". Second, we show how to compute a shortest geodesic path between two points in a simple polygon in quadratic time and with constant work-space. | |||||||
| 権利 | ||||||||
| 権利情報 | Copyright © Brown University, Journal of Graph Algorithms and Applications | |||||||
| 著者版フラグ | ||||||||
| 出版タイプ | VoR | |||||||
| 出版タイプResource | http://purl.org/coar/version/c_970fb48d4fbd8a85 | |||||||
| 関連URI | ||||||||
| 識別子タイプ | URI | |||||||
| 関連識別子 | https://www.brown.edu/ | |||||||
| 関連名称 | https://www.brown.edu/ | |||||||
| 関連URI | ||||||||
| 識別子タイプ | URI | |||||||
| 関連識別子 | http://jgaa.info/getPaper?id=240 | |||||||
| 関連名称 | http://jgaa.info/getPaper?id=240 | |||||||
