Speaker: Speaker: Rob H. Bisseling (Utrecht University) http://www.staff.science.uu.nl/~bisse101/
Title: Parallel matching for big graphs
Abstract: We present a gentle introduction to the topic of parallelising graph algorithms through the example of an approximation algorithm for matching in big weighted graphs. This algorithm is based on locally dominant edges and partial edge sorting.
We will discuss how to parallelise the algorithm with special attention to load balancing in an irregular setting, tie-breaking between edge weights as a feature, not a bug, and the virtues of 2D (edge) vs. 1D (vertex) partitioning.
We use the Bulk Synchronous Parallel (BSP) model to structure the computation, to analyse the time complexity, and to reason about the correctness of the algorithm.
