Faster exponential-time algorithms for approximately counting independent sets
From MaRDI portal
Publication:2235762
DOI10.1016/j.tcs.2021.09.009OpenAlexW3196476531WikidataQ115566726 ScholiaQ115566726MaRDI QIDQ2235762
John Lapinskas, Leslie Ann Goldberg, David Richerby
Publication date: 21 October 2021
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2005.05070
Related Items
Cites Work
- Exact exponential algorithms.
- Number of models and satisfiability of sets of clauses
- Counting models for 2SAT and 3SAT formulae
- The relative complexity of approximate counting problems
- Counting the number of solutions for instances of satisfiability
- Computational complexity of counting problems on 3-regular planar graphs
- Approximately Counting $H$-Colorings is $\#\mathrm{BIS}$-Hard
- Counting independent sets up to the tree threshold
- FPTAS for #BIS with Degree Bounds on One Side
- The Complexity of Counting Cuts and of Computing the Probability that a Graph is Connected
- A Tighter Bound for Counting Max-Weight Solutions to 2SAT Instances
- Approximating the Partition Function of the Ferromagnetic Potts Model
- Matchings and walks in graphs
- Algorithms for #BIS-hard problems on expander graphs
- Spatial mixing and the connective constant: Optimal bounds
- The expressibility of functions on the boolean domain, with applications to counting CSPs
- Ferromagnetic Potts Model: Refined #BIS-hardness and Related Results
- Algorithm 457: finding all cliques of an undirected graph
- Faster graph coloring in polynomial space
- Unnamed Item
