Counting spanning trees using modular decomposition

作     者：Nikolopoulos, Stavros D. Palios, Leonidas Papadopoulos, Charis 

作者机构：Univ Ioannina Dept Comp Sci & Engn GR-45110 Ioannina Greece Univ Ioannina Dept Math GR-45110 Ioannina Greece 

出 版 物：《THEORETICAL COMPUTER SCIENCE》 (理论计算机科学)

年 卷 期：2014年第526卷

页      面：41-57页

核心收录：

学科分类：08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主　　题：Number of spanning trees Modular decomposition Kirchhoff matrix tree theorem Linear-time algorithms (q, q-4)-graph P-4-tidy graph Tree-cograph 

摘      要：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)-graph for fixed q, a 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. (C) 2014 Elsevier B.V. All rights reserved.