15 citations · 16 across the 3 of their papers we have counts for
7 papers
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…
Pebbles, Graphs, and a Pinch of Combinatorics: Towards Tight I/O Lower Bounds for Statically Analyzable Programs
Grzegorz Kwasniewski, Tal Ben-Nun, Lukas Gianinazzi +5
Determining I/O lower bounds is a crucial step in obtaining communication-efficient parallel algorithms, both across the memory hierarchy and between processors. Current approaches…
SISA: Set-Centric Instruction Set Architecture for Graph Mining on Processing-in-Memory Systems
Maciej Besta, Raghavendra Kanakagiri, Grzegorz Kwasniewski +15
Simple graph algorithms such as PageRank have been the target of numerous hardware accelerators. Yet, there also exist much more complex graph mining algorithms for problems such 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…