Abstract

The approximate single-source shortest-path problem is as follows: given a graph with non-negative edge weights and a designated source vertex s, return estimates of the distances from s to each other vertex such that the estimate falls between the true distance and (1 + ?) times the distance. Our result is the first nearly work-efficient parallel algorithm with sublinear span (also called depth) for the approximate shortest-path problem on directed graphs. Specifically, for constant ? and polynomially-bounded edge weights, our algorithm has work O ?(m) and span n1/2+o(1). Several algorithms were previously known for the case of undirected graphs, but none of the techniques seem to translate to the directed setting. The main technical contribution is the first nearly linear-work algorithm for constructing hopsets on directed graphs. A (?,?)-hopset is a set of weighted edges (sometimes called shortcuts) which, when added to the graph, admit ?-hop paths with weight no more than (1+?) times the true shortest-path distances. There is a simple sequential algorithm that takes as input a directed graph and produces a linear-cardinality hopset with ? = O( n), but its running time is quite high--specifically O ?(m?n). Our algorithm is the first more efficient algorithm that produces a directed hopset with similar characteristics. Specifically, our sequential algorithm runs in O ?(m) time and constructs a hopset with O ?(n) edges and ? = n1/2+o(1). A parallel version of the algorithm has work O ?(m) and span n1/2+o(1).

Biography

Katina Russell is a Ph.D. candidate in the Department of Computer Science at Georgetown University. She is advised by professor Jeremy T. Fineman. Before Georgetown, Katina received her masters degree in computer science from Tufts University, and her bachelors degree in math from Boston College. Her current research focuses on graph algorithms, parallel algorithms, and data structures.