Approximating the Arboricity in Sublinear Time

Talya Eden, Saleet Mossel, Dana Ron

We consider the problem of approximating the arboricity of a graph $G=(V,E)$, which we denote by $\mathsf{arb}(G)$, in sublinear time, where the arboricity of a graph is the minim…