Deterministic Girth Approximation in Weighted Undirected Graphs

We give deterministic algorithms for approximating the girth~$g$ of an undirected graph with $n$ vertices, $m$ edges, and nonnegative real edge lengths. For every integer $k\geq2$, our algorithm returns a cycle of length at most $\frac{2k}{3}g$ in $O((m+n^{1+2/k})k\log n)$ worst-case time. For every