10. – 15. Juni 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)

Auskunft zu diesem Dagstuhl-Seminar erteilt

Dagstuhl Service Team


Dagstuhl Report, Volume 8, Issue 6 Dagstuhl Report


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 der Reihe Dagstuhl Reports werden alle Dagstuhl-Seminare und Dagstuhl-Perspektiven-Workshops dokumentiert. Die Organisatoren stellen zusammen mit dem Collector des Seminars einen Bericht zusammen, der die Beiträge der Autoren zusammenfasst und um eine Zusammenfassung ergänzt.


Download Übersichtsflyer (PDF).

Dagstuhl's Impact

Bitte informieren Sie uns, wenn eine Veröffentlichung ausgehend von Ihrem Seminar entsteht. Derartige Veröffentlichungen werden von uns in der Rubrik Dagstuhl's Impact separat aufgelistet  und im Erdgeschoss der Bibliothek präsentiert.


Es besteht weiterhin die Möglichkeit, eine umfassende Kollektion begutachteter Arbeiten in der Reihe Dagstuhl Follow-Ups zu publizieren.