New algorithms for girth and cycle detection

Liam Roditty, Plia Trabelsi

Let $G=(V,E)$ be an unweighted undirected graph with $n$ vertices and $m$ edges. Let $g$ be the girth of $G$, that is, the length of a shortest cycle in $G$. We present a randomize…