483 citations · 588 across the 24 of their papers we have counts for
7 papers · 1 filter
Maximum Flows in Parametric Graph Templates
Tal Ben-Nun, Lukas Gianinazzi, Torsten Hoefler +1
Execution graphs of parallel loop programs exhibit a nested, repeating structure. We show how such graphs that are the result of nested repetition can be represented by succinct pa…
The spatial computer: A model for energy-efficient parallel computation
Lukas Gianinazzi, Tal Ben-Nun, Maciej Besta +4
We present a new parallel model of computation suitable for spatial architectures, for which the energy used for communication heavily depends on the distance of the communicating…
Parallel Algorithms for Finding Large Cliques in Sparse Graphs
Lukas Gianinazzi, Maciej Besta, Yannick Schaffner +1
We present a parallel k-clique listing algorithm with improved work bounds (for the same depth) in sparse graphs with low degeneracy or arboricity. We achieve this by introducing a…
Parametric Graph Templates: Properties and Algorithms
Tal Ben-Nun, Lukas Gianinazzi, Torsten Hoefler +1
Hierarchical structure and repetition are prevalent in graphs originating from nature or engineering. These patterns can be represented by a class of parametric-structure graphs, w…
High-Performance Parallel Graph Coloring with Strong Guarantees on Work, Depth, and Quality
Maciej Besta, Armon Carigiet, Zur Vonarburg-Shmaria +3
We develop the first parallel graph coloring heuristics with strong theoretical guarantees on work and depth and coloring quality. The key idea is to design a relaxation of the ver…
Parallel Planar Subgraph Isomorphism and Vertex Connectivity
Lukas Gianinazzi, Torsten Hoefler
We present the first parallel fixed-parameter algorithm for subgraph isomorphism in planar graphs, bounded-genus graphs, and, more generally, all minor-closed graphs of locally bou…
Slim Graph: Practical Lossy Graph Compression for Approximate Graph Processing, Storage, and Analytics
Maciej Besta, Simon Weber, Lukas Gianinazzi +4
We propose Slim Graph: the first programming model and framework for practical lossy graph compression that facilitates high-performance approximate graph processing, storage, and…