On the Locality of Nash-Williams Forest Decomposition and Star-Forest Decomposition

David G. Harris, Hsin-Hao Su, Hoa T. Vu

Given a graph $G=(V,E)$ with arboricity $\alpha$, we study the problem of decomposing the edges of $G$ into $(1+\epsilon )\alpha$ disjoint forests in the distributed LOCAL model. Barenboim and Elkin…