Constant-Work-Space Algorithms for Shortest Paths in Trees and Simple Polygons - Asano, Tetsuo; Mulzer, Wolfgang; Wang, Yajun (Journal of Graph Algorithms and Applications, 2011)
Constant-work-space algorithms model computation when space isat a premium: the input is given as a read-only array that allowsrandom access to its entries, and the algorithm may useconstantly many additional registers of O(logn) bits each, wheren denotes the input size. <!----> We present such algorithms for two restricted variants of the shortestpath problem.First, we describe how to report a simple path between two arbitrary nodesin a given tree.Using a technique called "computing instead of storing", we obtaina naive algorithm that needs quadratic time and a constant numberof additional registers.We then show how to improve the running time tolinear by applying a technique named "simulated parallelization".Second, we show how to compute a shortest geodesic path between two points ina simple polygon in quadratic time and with constant work-space. <!---->