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.

Creative Commons BY 3.0 DE

Henning Meyerhenke, Richard Peng, Ali Pinar, and Ilya Safro

• Nesreen Ahmed (Intel Labs - Santa Clara, US) [dblp]
• Eugenio Angriman (Universität Köln, DE) [dblp]
• David A. Bader (Georgia Institute of Technology - Atlanta, US) [dblp]
• Maciej Besta (ETH Zürich, CH) [dblp]
• Rob Bisseling (Utrecht University, NL) [dblp]
• Timothy Chu (Carnegie Mellon University - Pittsburgh, US) [dblp]
• Pierluigi Crescenzi (University of Florence, IT) [dblp]
• Timothy Alden Davis (Texas A&M University - College Station, US) [dblp]
• Irene Finocchi (Sapienza University of Rome, IT) [dblp]
• John Gilbert (University of California - Santa Barbara, US) [dblp]
• David F. Gleich (Purdue University - West Lafayette, US) [dblp]
• Riko Jacob (IT University of Copenhagen, DK) [dblp]
• George Karypis (University of Minnesota - Minneapolis, US) [dblp]
• Michel A. Kinsy (Boston University, US) [dblp]
• Marsha Kleinbauer (TU Kaiserslautern, DE) [dblp]
• Christine Klymko (LLNL - Livermore, US) [dblp]
• Yiannis Koutis (NJIT - Newark, US) [dblp]
• Danai Koutra (University of Michigan - Ann Arbor, US) [dblp]
• Rasmus Kyng (Harvard University - Cambridge, US) [dblp]
• Nelly Litvak (University of Twente, NL) [dblp]
• Fredrik Manne (University of Bergen, NO) [dblp]
• Henning Meyerhenke (HU Berlin, DE) [dblp]
• Marco Minutoli (Pacific Northwest National Lab. - Richland, US) [dblp]
• Lalla Mouatadid (University of Toronto, CA) [dblp]
• Danupon Nanongkai (KTH Royal Institute of Technology - Stockholm, SE) [dblp]
• Lorenzo Orecchia (Boston University, US) [dblp]
• Richard Peng (Georgia Institute of Technology - Atlanta, US) [dblp]
• Manuel Penschuck (Goethe-Universität - Frankfurt a. M., DE) [dblp]
• Cynthia A. Phillips (Sandia National Labs - Albuquerque, US) [dblp]
• Alex Pothen (Purdue University - West Lafayette, US) [dblp]
• Maria Predari (Universität Köln, DE) [dblp]
• Vijaya Ramachandran (University of Texas - Austin, US) [dblp]
• Sushant Sachdeva (University of Toronto, CA) [dblp]
• Ilya Safro (Clemson University, US) [dblp]
• Peter Sanders (KIT - Karlsruher Institut für Technologie, DE) [dblp]
• Christian Schulz (Universität Wien, AT) [dblp]
• Julian Shun (MIT - Cambridge, US) [dblp]
• Blair D. Sullivan (North Carolina State University - Raleigh, US) [dblp]
• Charalampos E. Tsourakakis (Harvard University - Cambridge, US) [dblp]