We study the parallel complexity of computing the arboricity of a graph, defined as the minimum number of forests into which its edges can be partitioned.
For graphs of bounded treewidth, we present a simple dynamic programming–based parallel algorithm that constructs an optimal partition of the edges into forests.
For ... more >>>