Constant Approximation of Arboricity in Near-Optimal Sublinear Time

Jiangqi Dai, Mohsen Ghaffari, Julian Portmann

We present a randomized algorithm that computes a constant approximation of a graph's arboricity, using $\tilde{O}(n/\hat{I}»)$ queries to adjacency lists and in the same time bound. Her…