Seminar: Scalable Parallel Graph Algorithms

  • Type: Seminar (S)
  • Semester: SS 2020
  • Time: 20.04.2020
    09:45 - 11:15 wöchentlich
    50.34 Raum 131
    50.34 INFORMATIK, Kollegiengebäude am Fasanengarten
    weitere...

  • Lecturer: Prof. Dr. Peter Sanders
    Sebastian Lamm
    Tobias Maier
  • SWS: 2
  • Lv-No.: 2400033
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)