http://www.dagstuhl.de/18241

June 10 – 15 , 2018, Dagstuhl Seminar 18241

High-Performance Graph Algorithms

Organizers

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)

For support, please contact

Annette Beyer for administrative matters

Andreas Dolzmann for scientific matters

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

Book exhibition

Books from the participants of the current Seminar 

Book exhibition in the library, ground floor, during the seminar week.

Documentation

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

Publications

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

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.

NSF young researcher support