Work Efficient Parallel Algorithms for Spanners and Hopsets
November 25, 2015

Problems about distances in graphs have proved to be difficult to parallelize. Compared to the sequential results, we often lose out in at least one aspect of solution quality, work, or depth. In this talk we give an approach that is centered around a graph decompositions scheme. We will describe a parallel graph clustering algorithm using exponential start time, and apply it to obtain work efficient spanner construction and the shortest path distance approximation

Presented in Partial Fulfillment of the CSD Speaking Skills Requirement.