Exponential Time Complexity of Weighted Counting of Independent Sets
DOI10.1007/978-3-642-17493-3_18zbMath1309.68094arXiv1007.1146OpenAlexW1904620001MaRDI QIDQ3058702
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
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)
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(20.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