Counting spanning trees using modular decomposition

DOI10.1016/J.TCS.2014.01.012zbMATH Open1283.05134OpenAlexW2049204396MaRDI QIDQ2437761FDOQ2437761

Authors: Stavros D. Nikolopoulos, Leonidas Palios, Charis Papadopoulos 

Publication date: 13 March 2014

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2014.01.012

Recommendations

• Counting spanning trees in graphs using modular decomposition
• Counting spanning trees in cographs: an algorithmic approach
• scientific article
• \(P_ 4\)-trees and substitution decomposition
• Enumeration of spanning trees of certain graphs

zbMATH Keywords

modular decompositionlinear-time algorithms\(P_4\)-tidy graphnumber of spanning treestree-cograph\((q,q-4)\)-graphKirchhoff matrix tree theorem

Mathematics Subject Classification ID

Trees (05C05) Graph algorithms (graph-theoretic aspects) (05C85) Enumeration in graph theory (05C30)

Cites Work

• Generalized Nested Dissection
• Matching theory
• Title not available (Why is that?)
• Title not available (Why is that?)
• Modular decomposition and transitive orientation
• A new technique for the characterization of graphs with a maximum number of spanning trees
• Linear time solvable optimization problems on graphs of bounded clique-width
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• A New Class of Brittle Graphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• (\(P_{5}\), diamond)-free graphs revisited: Structure and linear time optimization.
• On the number of spanning trees of multi-star related graphs
• A formula for the number of spanning trees of a multi-star related graph
• Uniformly-most reliable networks do not always exist
• The number of spanning trees in \(K_ n\)-complements of quasi-threshold graphs
• On the structure of graphs with few \(P_4\)s
• A survey of the algorithmic aspects of modular decomposition
• The number of spanning trees in circulant graphs
• Chebyshev polynomials and spanning tree formulas for circulant and related graphs
• Simpler Linear-Time Modular Decomposition Via Recursive Factorizing Permutations
• Tree- and forest-perfect graphs
• Efficient algorithms for graphs with few \(P_4\)'s
• Strong tree-cographs are Birkhoff graphs
• On semi-\(P_ 4\)-sparse graphs
• Computing the treewidth and the minimum fill-in with the modular decomposition
• Laplacian spectrum of weakly quasi-threshold graphs
• Some methods for counting the spanning trees in labelled molecular graphs, examined in relation to certain fullerenes
• An efficient approach for counting the number of spanning trees in circulant and related graphs
• Maximizing the number of spanning trees in \(K_n\)-complements of asteroidal graphs
• A new approach to solving three combinatorial enumeration problems on planar graphs
• Drawing graphs using modular decomposition

Cited In (4)

• The number and degree distribution of spanning trees in the Tower of Hanoi graph
• The number of spanning trees for Sierpiński graphs and data center networks
• Counting spanning trees in cographs: an algorithmic approach
• Counting spanning trees in graphs using modular decomposition

This page was built for publication: Counting spanning trees using modular decomposition

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2437761)