Parallel Connectivity and Shortest Paths
Date:
Near-linear work algorithms for connectivity and single-source shortest paths (SSSP) have been known since before the 1950s. In this talk, we will describe approaches to increase their parallelism, including coarsening algorithms for connectivity, and incremental stepping algorithms for SSSP.