Home  | Impressum | Datenschutz | Sitemap | KIT

Seminar: Scalable Parallel Graph Algorithms

Seminar: Scalable Parallel Graph Algorithms
Typ: Seminar (S)
Semester: SS 2020

Geb. 50.34, Raum 131


Montag 09:45 - 11:15

Dozent: Prof. Dr. Peter Sanders
Sebastian Lamm
Tobias Maier
SWS: 2
LVNr.: 2400033

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)