  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 GPU. We focus on two established applications of
the technique: (1) the problem of finding lowest common ancestors (LCA) of
pairs of nodes in trees, and (2) the problem of finding bridges in undirected
graphs. In our experiments, we compare theoretically optimal algorithms using
the Euler tour technique against simpler heuristics supposed to perform
particularly well on typical instances. We show that the Euler tour-based
algorithms not only fulfill their theoretical promises and outperform practical
heuristics on hard instances, but also perform on par with them on easy
instances.
