# 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.