Short Cycles via Low-Diameter Decompositions

Yang P. Liu, Sushant Sachdeva, Zejun Yu

We present improved algorithms for short cycle decomposition of a graph. Short cycle decompositions were introduced in the recent work of Chu et al, and were used to make progress…