We will investigate the best known algorithm for solving fundamental graph problems on parallel computers. This includes both shared memory and distributed memory approaches. 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)