Home | Issues | About JGAA | Instructions for Authors |
Special Issue on Selected Papers from the Fourth International Workshop on Algorithms and Computation (WALCOM 2010)
DOI: 10.7155/jgaa.00240
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.
|
Journal Supporters
|