Computing the numbers of independent sets and matchings of all sizes for graphs with bounded treewidth

DOI10.1016/j.amc.2018.03.017zbMath1427.05170OpenAlexW2794749612WikidataQ130060574 ScholiaQ130060574MaRDI QIDQ2333222

Pengfei Wan, Jian-hua Tu, Bin Long Li, Sheng Gui Zhang

Publication date: 12 November 2019

Published in: Applied Mathematics and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.amc.2018.03.017

zbMATH Keywords

dynamic programmingmatchingtreewidthindependent set

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (3)

On the intersection graph of the disks with diameters the sides of a convex \(n\)-gon ⋮ Orderings of a class of trees with respect to the Merrifield-Simmons index and the Hosoya index ⋮ Independence polynomials of bipartite graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Entropy and the complexity of graphs revisited
• Probabilistic inequalities for evaluating structural network measures
• Maxima and minima of the Hosoya index and the Merrifield-Simmons index
• A history of graph entropy measures
• Counting independent sets in tree convex bipartite graphs
• Counting the number of independent sets in chordal graphs
• Information processing in complex networks: Graph entropy and information functionals
• Independent sets in regular graphs and sum-free subsets of finite groups
• Treewidth. Computations and approximations
• Linear-time algorithms for counting independent sets in bipartite permutation graphs
• Network entropies based on independent sets and matchings
• An Entropy Approach to the Hard-Core Model on Bipartite Graphs
• The Complexity of Counting Cuts and of Computing the Probability that a Graph is Connected
• Graph minors. II. Algorithmic aspects of tree-width
• Parameterized Algorithms
• Entropy and the complexity of graphs: I. An index of the relative complexity of a graph
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth

This page was built for publication: Computing the numbers of independent sets and matchings of all sizes for graphs with bounded treewidth