Seminar: Parallel Graph Algorithms


We will investigate the best known algorithm for solving fundamental graph problems on parallel computers. This includes both shared memory and distributed memory approaches. The typical contribution will be a synthesis of several papers on one graph problem.

Example problems are

  • connected components
  • minimum spanning trees
  • coloring
  • strongly connected components
  • breadth-first-search
  • maximum flows
  • matchings
  • graph partitioning
  • graph clustering
  • shortest paths
  • ear-decomposition and its applications
  • Delaunay triangulation
  • graph generators
  • reachability data structures
  • centrality measures (e.g., betweenness)