A Strongly Subcubic Combinatorial Algorithm for Triangle Detection with Applications

Adrian Dumitrescu

We revisit the algorithmic problem of finding a triangle in a graph: We give a randomized combinatorial algorithm for triangle detection in a given $n$-vertex graph with $m$ edges…