ICS Theory Group

ICS 269, Spring 2005: Theory Seminar

4 Feb 2005:
Finding an Optimal Path without Growing the Tree by Danny Z. Chen, Ovidiu Daescu, Xiaobo (Sharon) Hu, and Jinhui Xu
Presented by Michael Shindler

Abstract: It is well known that any algorithm to compute the shortest path between any two vertices in a graph must take the same asymptotic time as an algorithm that computers a single-source all-destinations tree. But space complexity is another matter. The authors develop an algorithm paradigm for reporting an optimal path between two vertices without growing an entire single-source all-destinations tree. This brings forth a new technique, prune and search, and a new data structure, the clipped tree. These are used to improve the space bounds on previously best known algorithms.

This paper appeared in Journal of Algorithms 49:1 (October 2003), pp. 13-41.