Correlation decay and deterministic FPTAS for counting list-colorings of a graph

zbMATH Open1302.05187arXivmath/0606143MaRDI QIDQ2934720FDOQ2934720

Authors:

Publication date: 18 December 2014

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

Recommendations

• Correlation decay and deterministic FPTAS for counting colorings of a graph
• Deterministic counting of graph colourings using sequences of subgraphs
• Approximate counting via correlation decay in spin systems
• Improved FPTAS for multi-spin systems
• An FPTAS for counting proper four-colorings on cubic graphs

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Coloring of graphs and hypergraphs (05C15)

Cited In (15)

• Sublinear-time algorithms for monomer-dimer systems on bounded degree graphs
• Deterministic counting of graph colourings using sequences of subgraphs
• Spatial mixing and the connective constant: optimal bounds
• Correlation decay and deterministic FPTAS for counting colorings of a graph
• Zero-free regions of partition functions with applications to algorithms and graph limits
• Improved FPTAS for multi-spin systems
• An FPTAS for counting proper four-colorings on cubic graphs
• Spectral independence in high-dimensional expanders and applications to the hardcore model
• Sequential cavity method for computing free energy and surface pressure
• Title not available (Why is that?)
• Approximate counting via correlation decay in spin systems
• Approximate counting via correlation decay on planar graphs
• A deterministic approximation algorithm for computing the permanent of a 0, 1 matrix
• Approximating the volume of unions and intersections of high-dimensional geometric objects
• An FPTAS for the volume of some \(\mathcal{V} \)-polytopes -- it is hard to compute the volume of the intersection of two cross-polytopes

This page was built for publication: Correlation decay and deterministic FPTAS for counting list-colorings of a graph

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2934720)