Constant-Work-Space Algorithms for Shortest Paths in Trees and Simple Polygons
Vol. 15, no. 5, pp. 569-586, 2011. Regular paper.
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 access 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.
Submitted: April 2010.
Reviewed: November 2010.
Revised: December 2010.
Accepted: May 2011.
Final: May 2011.
Published: October 2011.
Communicated by Md. Saidur Rahman and Satoshi Fujita
article (PDF)