483 citations · 560 across the 20 of their papers we have counts for
3 papers · 1 filter
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…