Institut für Theoretische Informatik, Algorithmik II

Seminar: Scalable Parallel Graph Algorithms

Bemerkungen

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)