Parallel Graph Algorithms

ACO Student Seminar
Friday, September 23, 2016 - 13:05
1 hour (actually 50 minutes)
Skiles 005
College of Computing, Georgia Tech
Parallel algorithms study ways of speeding up sequential algorithms by splitting work onto multiple processors. Theoretical studies of parallel algorithms often focus on performing a small number of operations, but assume more generous models of communication. Recent progresses led to parallel algorithms for many graph optimization problems that have proven to be difficult to parallelize. In this talk I will survey routines at the core of these results: low diameter decompositions, random sampling, and iterative methods.