Constructive Arboricity in Almost-Linear Time for Dense Graphs
The arboricity of a graph is the minimum number of forests needed to partition its edges. We present a randomized algorithm that computes the exact arboricity of a simple graph and constructs an optimal forest partition in $\min\{n^{2+o(1)},m^{4/3+o(1)}\}$ time both in expectation and with high probability, where $n$ a...