On Counting Independent Sets in Sparse Graphs
From MaRDI portal
Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40)
Recommendations
Cited in
(66)- On the hardness of sampling independent sets beyond the tree threshold
- The complexity of counting colourings and independent sets in sparse graphs and hypergraphs
- Sparse hypergraphs with low independence number
- Perfect sampling using bounding chains.
- The complexity of approximating bounded-degree Boolean \(\#\)CSP
- Counting families of mutually intersecting sets
- Mixing of Markov chains for independent sets on chordal graphs with bounded separators
- Notes on computational hardness of hypothesis testing: predictions using the low-degree likelihood ratio
- Fair splittings by independent sets in sparse graphs
- Tight bounds for mixing of the Swendsen-Wang algorithm at the Potts transition point
- A general lower bound for mixing of single-site dynamics on graphs
- Systematic scan for sampling colorings
- Approximation algorithms for two-state anti-ferromagnetic spin systems on bounded degree graphs
- A dichotomy for bounded degree graph homomorphisms with nonnegative weights
- The complexity of counting in sparse, regular, and planar graphs
- A graph polynomial for independent sets of bipartite graphs
- A graph polynomial for independent sets of bipartite graphs
- Counting independent sets up to the tree threshold
- Sequential Monte Carlo for counting vertex covers in general graphs
- On systematic scan for sampling H-colorings of the path
- Rapid mixing of Gibbs sampling on graphs that are sparse on average
- The mixing time of Glauber dynamics for coloring regular trees
- Counting independent sets using the Bethe approximation
- Simulated tempering and swapping on mean-field models
- MULTI-TERMINAL NETWORK CONNECTEDNESS ON SERIES-PARALLEL NETWORKS
- The complexity of approximately counting in 2-spin systems on k-uniform bounded-degree hypergraphs
- Model counting of monotone conjunctive normal form formulas with spectra
- Sampling independent sets in the discrete torus
- A counterexample to rapid mixing of the Ge-Stefankovic process
- A dichotomy theorem for the approximate counting of complex-weighted bounded-degree Boolean CSPs
- scientific article; zbMATH DE number 1559584 (Why is no real title available?)
- On the Lovász Theta Function for Independent Sets in Sparse Graphs
- On the $b$ -Independence Number of Sparse Random Graphs
- On Markov Chains for Independent Sets
- Counting constraint satisfaction problems
- Counting weighted independent sets beyond the permanent
- Counting homomorphisms to trees modulo a prime
- Spectral independence in high-dimensional expanders and applications to the hardcore model
- A spectral independence view on hard spheres via block dynamics
- Approximately counting paths and cycles in a graph
- Stochastic enumeration method for counting trees
- Descriptive complexity for counting complexity classes
- Tunneling of the hard-core model on finite triangular lattices
- Inapproximability of the partition function for the antiferromagnetic Ising and hard-core models
- A Worst-Case Time Upper Bound for Counting the Number of Independent Sets
- Phase coexistence and torpid mixing in the 3-coloring model on \({\mathbb Z}^d\)
- Approximate counting via correlation decay in spin systems
- Approximation algorithms for two-state anti-ferromagnetic spin systems on bounded degree graphs
- Counting Independent Sets and Colorings on Random Regular Bipartite Graphs
- Gibbs rapidly samples colorings of \(G(n, d/n)\)
- Counting maximal independent sets in some \(n\)-gonal cacti
- Counting independent sets in graphs with bounded bipartite pathwidth
- Homomorphisms from the torus
- Lifted algorithms for symmetric weighted first-order model sampling
- Mixing time of exponential random graphs
- The low-degree hardness of finding large independent sets in sparse random hypergraphs
- A dichotomy for bounded degree graph homomorphisms with nonnegative weights
- Fast and slow mixing of the Kawasaki dynamics on bounded-degree graphs
- Fast and slow mixing of the Kawasaki dynamics on bounded-degree graphs
- Low coordinate degree algorithms. I: Universality of computational thresholds for hypothesis testing
- Bounded degree nonnegative counting CSP
- Inapproximability of counting hypergraph colourings
- H-coloring tori
- A spectral independence view on hard spheres via block dynamics
- Time lower bounds for the Metropolis process and simulated annealing
- Limitations of Markov chain Monte Carlo algorithms for Bayesian inference of phylogeny
This page was built for publication: On Counting Independent Sets in Sparse Graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3149880)
