Counting spanning trees using modular decomposition ?
In this paper we present an algorithm for determining the number of spanning trees of a graph G which takes advantage of the structure of the modular decomposition tree of G. Specifically, our algorithm works by contracting the modular decomposition tree of the input graph G in a bottom-up fashion until it becomes a single node; then, the number of spanning trees of G is computed as the product of a collection of values which are associated with the vertices of G  and are updated during the contraction process. In particular, when applied on a (q,q?4) ( q , q ? 4 ) -graph for fixed q , a P4 P 4 -tidy graph, or a tree-cograph, our algorithm computes the number of its spanning trees in time linear in the size of the graph, where the complexity of arithmetic operations is measured under the uniform-cost criterion. Therefore we give the first linear-time algorithm for the counting problem in the considered graph classes.
modular decomposition number of spanning trees (q q?4) ( q q?4) ( q q?4) ( q q ? 4 ) linear-time algorithms kirchhoff matrix tree theorem q ? 4 ) -graph (q q ? 4 ) (q q ? 4 ) ( q p4 p 4 -tidy graph p4 p 4 p4 p 4 p 4 tree-cograph