Counting Spanning Trees in Cographs: An Algorithmic Approach (Journal article)

Nikolopoulos, S. D./ Papadopoulos, C.

In this paper we present a new simple linear-time algorithm for determining the number of spanning trees in the class of complement reducible graphs, also known as cographs; for a cograph G on n vertices and m edges, our algorithm computes the number of spanning trees, of G in O(n + m) time and space, where the complexity of arithmetic operations is measured under the uniform cost criterion. The algorithm takes advantage of the cotree of the input cograph G and works by contracting it 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. The correctness of our algorithm is established through the Kirchhoff matrix tree theorem, and also relies on structural and algorithmic properties of the class of cographs. We also extend our results to a proper superclass of cographs, namely the P(4)-reducible graphs. and show that the problem of finding the number of spanning trees of a P(4)-reducible graph has linear-time solution.
Institution and School/Department of submitter: Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μηχανικών Ηλεκτρονικών Υπολογιστών και Πληροφορικής
Keywords: cographs,p(4)-reducible graphs,number of spanning trees,modular decomposition,combinatorial problems,algorithms,complexity,recognition algorithm,threshold graphs,number,circulant
ISSN: 0381-7032
Appears in Collections:Άρθρα σε επιστημονικά περιοδικά ( Ανοικτά)

 Please use this identifier to cite or link to this item:
  This item is a favorite for 0 people.

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.