Deterministic counting of graph colourings using sequences of subgraphs
From MaRDI portal
Coloring of graphs and hypergraphs (05C15) Enumeration in graph theory (05C30) Random graphs (graph-theoretic aspects) (05C80) Graph algorithms (graph-theoretic aspects) (05C85) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25) Analysis of algorithms (68W40)
Recommendations
- Correlation decay and deterministic FPTAS for counting colorings of a graph
- Correlation decay and deterministic FPTAS for counting list-colorings of a graph
- A Simple Algorithm for Sampling Colorings of G(n,d/n) Up to The Gibbs Uniqueness Threshold
- Switching colouring of G(n,d/n) for sampling up to Gibbs uniqueness threshold
- A simple algorithm for random colouring G(n, d/n) using (2 + )d colours
Cites work
- A Simple Algorithm for Sampling Colorings of G(n,d/n) Up to The Gibbs Uniqueness Threshold
- Almost all regular graphs are hamiltonian
- Approximate counting, uniform generation and rapidly mixing Markov chains
- Approximation algorithms for two-state anti-ferromagnetic spin systems on bounded degree graphs
- Counting good truth assignments of random k-SAT formulae
- Counting independent sets up to the tree threshold
- Gibbs states and the set of solutions of random constraint satisfaction problems
- Graphical models, exponential families, and variational inference
- scientific article; zbMATH DE number 3812655 (Why is no real title available?)
- Improved bounds for sampling colorings
- Information, Physics, and Computation
- Local convergence of random graph colorings
- Planting colourings silently
- Random generation of combinatorial structures from a uniform distribution
- Random Regular Graphs: Asymptotic Distributions and Contiguity
- Rapid mixing of Gibbs sampling on graphs that are sparse on average
- Reconstruction/non-reconstruction thresholds for colourings of general Galton-Watson trees
- Sampling in Potts model on sparse random graphs
- Sampling random colorings of sparse random graphs
- The condensation phase transition in random graph coloring
Cited in
(3)
This page was built for publication: Deterministic counting of graph colourings using sequences of subgraphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4993106)
