Seminar: Scalable Parallel Graph Algorithms


We will investigate the best known algorithm for solving fundamental graph problems on parallel computers. Particular focus will be on scalability to a large number of processors. 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)