In this seminar we will investigate the best-known algorithms for solving fundamental graph problems on parallel computers.
This includes both shared and distributed memory approaches.
Graph problems which could be explored in this seminar are listed below:

• 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)

This list is not exhaustive. If you have another interesting graph problem in mind you would like to investigate parallel algorithms for feel free to propose it.

Some remarks on the course:

• You will be assigned one graph problem for which you will have to conduct a literature review on the state of the art of parallel algorithms solving it. This work will be documented in a written report (a synthesis/survey of the most relevant research papers) and a presentation. Additionally, there will be a peer-review process for your reports, i.e. each participant has to review the reports of other participants.
• There will be an introductory presentation at the first meeting on October 19th, in which we will briefly present the topics and answer all questions about the course that might arise.
• If you are interested in participating, you can just join the first meeting – preferably after sending us a short email (to Sebastian Lamm and Matthias Schimek) in which you let us know the topic(s) you are interested in the most or propose own graph problems.