The **arboricity** of an undirected graph is the minimum number of forests into which its edges can be partitioned. Equivalently it is the minimum number of spanning forests needed to cover all the edges of the graph.

Read more about Arboricity: Example, Arboricity As A Measure of Density, Algorithms, Related Concepts

### Other articles related to "arboricity":

**Arboricity**- Related Concepts

... The star

**arboricity**of a graph is the size of the minimum forest, each tree of which is a star (tree with at most one non-leaf node), into which the edges of the ... If a tree is not a star itself, its star

**arboricity**is two, as can be seen by partitioning the edges into two subsets at odd and even distances from the tree root respectively ... Therefore, the star

**arboricity**of any graph is at least equal to the

**arboricity**, and at most equal to twice the

**arboricity**...

Clique Problem - Algorithms - Cliques of Fixed Size

... time for this algorithm is proportional to the

... time for this algorithm is proportional to the

**arboricity**of the graph (a(G)) times the number of edges, which is O(m a(G)) ... Since the**arboricity**is at most O(m1/2), this algorithm runs in time O(m3/2) ... takes time proportional to the number of edges times the (k − 2)nd power of the**arboricity**...Main Site Subjects

Related Subjects

Related Phrases

Related Words