@article{oai:kanazawa-u.repo.nii.ac.jp:00056526,
 author = {浅野, 哲夫 and Asano, Tetsuo and Mulzer, Wolfgang and Wang, Yajun},
 issue = {5},
 journal = {Journal of Graph Algorithms and Applications},
 month = {},
 note = {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., 金沢大学},
 pages = {569--586},
 title = {Constant-work-space algorithms for shortest paths in trees and simple polygons},
 volume = {15},
 year = {2011}
}