Euler Meets GPU: Practical Graph Algorithms with Theoretical Guarantees

Adam Polak, Adrian Siwiec, Michał Stobierski

The Euler tour technique is a classical tool for designing parallel graph algorithms, originally proposed for the PRAM model. We ask whether it can be adapted to run efficiently on…