MAC Seminar, speaker Rob Bisseling (Utrecht University)

Speaker: Speaker: Rob H. Bisseling (Utrecht University) http://www.staff.science.uu.nl/~bisse101/ Title: Parallel matching for big graphs
  • When Dec 13, 2016 from 02:00 PM to 03:00 PM (Europe/Amsterdam / UTC100)
  • Where CWI, room L016
  • Web Visit external website
  • Add event to calendar iCal

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.