Exponential Time Complexity of Weighted Counting of Independent Sets

DOI10.1007/978-3-642-17493-3_18zbMath1309.68094arXiv1007.1146OpenAlexW1904620001MaRDI QIDQ3058702

Christian Hoffmann

Publication date: 7 December 2010

Published in: Parameterized and Exact Computation (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1007.1146

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Enumeration in graph theory (05C30) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (3)

Block interpolation: a framework for tight exponential-time counting complexity ⋮ Counting Solutions to Polynomial Systems via Reductions ⋮ The Exponential Time Complexity of Computing the Probability That a Graph Is Connected

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A two-variable interlace polynomial
• A multivariate interlace polynomial and its computation for graphs of bounded clique-width
• Random generation of combinatorial structures from a uniform distribution
• Clique polynomials and independent set polynomials of graphs
• A note on the Glauber dynamics for sampling independent sets
• Which problems have strongly exponential complexity?
• The repulsive lattice gas, the independent-set polynomial, and the Lovász local lemma
• A Fine-grained Analysis of a Simple Independent Set Algorithm
• Counting independent sets up to the tree threshold
• A measure & conquer approach for the analysis of exact algorithms
• A Bottom-Up Method and Fast Algorithms for max independent set
• Exponential Time Complexity of the Permanent and the Tutte Polynomial
• An O(2^0.304n) Algorithm for Solving Maximum Independent Set Problem
• Algorithms for maximum independent sets
• The Complexity of Enumeration and Reliability Problems
• Finding a Maximum Independent Set
• Chromatic Roots are Dense in the Whole Complex Plane
• On the Complexity of the Interlace Polynomial
• On Markov Chains for Independent Sets

This page was built for publication: Exponential Time Complexity of Weighted Counting of Independent Sets