http://www.dagstuhl.de/18241

10. – 15. Juni 2018, Dagstuhl Seminar 18241

High-Performance Graph Algorithms

Organisatoren

Henning Meyerhenke (KIT – Karlsruher Institut für Technologie, 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 erteilen

Annette Beyer zu administrativen Fragen

Andreas Dolzmann zu wissenschaftlichen Fragen

Motivation

Graphs (or networks) are a powerful abstraction of various phenomena that can be expressed as relations between entities. As such graph algorithms have been the subject of many research efforts. Recently, however, we see a qualitative change how graph algorithms are used in practice. This change is due to (i) the complex structures and the sizes of graphs in emerging applications and (ii) the computer systems on which graph problems are solved. Application areas driving this change are diverse. To name a few, consider microblogging services in social media, bioinformatics, routing in traffic networks, technology diffusion and decentralized trade in economics, and combinatorial scientific computing. These application areas have in common that the associated problem instances show massive scale and irregular or skewed distributions of structural and semantic properties of entities and their interactions.

We need novel algorithms to cope with the ever growing problem sizes. A major challenge in designing and implementing graph algorithms is the large gap between theoretical computational models and observed performances. Computer architectures are becoming increasingly parallel and heterogeneous. Yet, many design and analysis techniques focus on the sequential case, and many striking theoretical results do not transfer to efficient computational tools. To fully exploit emerging architectures, it is important to develop parallel algorithms and tools with the specific hardware in mind.

This Dagstuhl Seminar aims at narrowing the gap between theoretical and practical graph algorithms. To this end, we would like to bring together (i) theoretical computer scientists whose works have strong practical context, (ii) researchers from graph-focused high performance computing, and (iii) algorithm engineers whose work falls in between the two previous areas. The invited practitioners in graph algorithms will also represent the domain expertise in applications and high-performance tools that address real-life graph problems. Two areas of high-performance graph algorithms that we plan to focus on are algorithmic network analysis and combinatorial scientific computing.

We would like to discuss and achieve some of the synergies that become possible from bringing the aforementioned fields closer together. One open research question covered will be how to transfer provably efficient theoretical methods into code that runs efficiently on modern parallel hardware. By bringing together experts from different fields, we hope to develop the next-generation tools of the trade for large graphs. These tools ideally are significantly faster and more feature-rich than the current state of the art, more closely connected with recent theoretical breakthroughs, and have more simplified development processes. This, in turn, will allow domain scientists to process larger data sets more effectively, and allow them to tackle problems previously out of reach.

Some topics for which we expect joint interest include (but are not limited to): solvers for graph-induced (non)linear systems of equations, I/O and communication efficiency of graph algorithms, fast analysis of massive complex networks, worst-case complexity vs empirical running time of graph algorithms, combinatorial scientific computing, and accelerating numerical methods for graphs.

License
  Creative Commons BY 3.0 DE
  Henning Meyerhenke, Richard Peng, Ali Pinar, and Ilya Safro

Related Dagstuhl Seminar

Classification

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

Keywords

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

Buchausstellung

Bücher der Teilnehmer 

Buchausstellung im Erdgeschoss der Bibliothek

(nur in der Veranstaltungswoche).

Dokumentation

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

Publikationen

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

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.