June 10 – 15 , 2018, Dagstuhl Seminar 18241

High-Performance Graph Algorithms


Henning Meyerhenke (HU Berlin, DE)
Richard Peng (Georgia Institute of Technology – Atlanta, US)
Ali Pinar (Sandia Nat. Labs – Livermore, US)
Ilya Safro (Clemson University, US)

For support, please contact

Dagstuhl Service Team


Dagstuhl Report, Volume 8, Issue 6 Dagstuhl Report
Aims & Scope
List of Participants


Many presentations in this Dagstuhl seminar emphasized recent trends regarding typical inputs and their effect on graph algorithm development. From a high-level perspective, one can divide the presentations into two categories: either more focused on algorithm theory or more focused on practical algorithmic results. Many talks considered both theoretical and practical aspects. Furthermore, attention was given to intermix talks with theoretical and practically motivated starting points in order to encourage discussions among attendees. We were happy to see such discussions, as well as synergy of both aspects, carrying over to working groups on open problems.

Theory-focused talks were given by Sachdeva, Nanongkai, Jacob, Mouatadid, Kyng, Tsourakakis, and Litvak. They considered numerous topics such as Laplacian solvers and related optimization techniques, dynamic graph algorithms, external-memory graph algorithms, graph decompositions, and generative models.

The talks with emphasis on practical performance can be further subdivided into three subclasses: (i) graph mining, network analysis and optimization, (ii) parallel, distributed and streaming graph algorithms and (iii) graph generation. The talks given by Koutra, Ahmed, Klymko, Angriman, Gleich and Schulz fall into the first subclass, with a wide variation of algorithmic problems under consideration. Likewise, it was interesting to see the variety in computing platforms and tools (for example shared memory, message passing, distributed systems, streaming from databases, GraphBLAS) used in the eight talks of subclass two, presented by Besta, Shun, Predari, Ramachandran, Pothen, Bader, Finocchi and Davis. Finally, the talks by Phillips, Sanders and Penschuck as well as Crescenzi dealt with generating very large graphs with properties also found in real-world graphs - which is important, among others, for convincing scaling studies in algorithm engineering.

Summary text license
  Creative Commons BY 3.0 Unported license
  Henning Meyerhenke, Richard Peng, and Ilya Safro

Dagstuhl Seminar Series


  • Data Structures / Algorithms / Complexity
  • Networks
  • Optimization / Scheduling


  • Graph algorithms
  • Algorithm engineering
  • High-performance computing
  • Combinatorial scientific computing
  • Theoretical computer science


In the series Dagstuhl Reports each Dagstuhl Seminar and Dagstuhl Perspectives Workshop is documented. The seminar organizers, in cooperation with the collector, prepare a report that includes contributions from the participants' talks together with a summary of the seminar.


Download overview leaflet (PDF).

Dagstuhl's Impact

Please inform us when a publication was published as a result from your seminar. These publications are listed in the category Dagstuhl's Impact and are presented on a special shelf on the ground floor of the library.


Furthermore, a comprehensive peer-reviewed collection of research papers can be published in the series Dagstuhl Follow-Ups.