Computing the numbers of independent sets and matchings of all sizes for graphs with bounded treewidth
From MaRDI portal
Publication:2333222
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
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