scientific article; zbMATH DE number 7204480

DOI10.4230/LIPICS.ICALP.2017.28MaRDI QIDQ5111358zbMATHFDO

Authors Andreas Galanis, Leslie Ann Goldberg, D. Štefankovič

Publication date 27 May 2020

zbMATH Keywords

approximate countingindependent set polynomialShearer threshold

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Recommendations

• Computing the independence polynomial: from the tree threshold down to the roots
• Implementations and the independent set polynomial below the Shearer threshold
• Inapproximability of the independent set polynomial in the complex plane

Cited in

(11)

• A spectral independence view on hard spheres via block dynamics
• Deterministic polynomial-time approximation algorithms for partition functions and graph polynomials
• Inapproximability of the independent set polynomial in the complex plane
• Counting independent sets in amenable groups
• Inapproximability of the independent set polynomial in the complex plane
• On a conjecture of Sokal concerning roots of the independence polynomial
• scientific article; zbMATH DE number 7559110 (Why is no real title available?)
• Zeros, chaotic ratios and the computational complexity of approximating the independence polynomial
• Computing the independence polynomial: from the tree threshold down to the roots
• Implementations and the independent set polynomial below the Shearer threshold
• Deterministic polynomial-time approximation algorithms for partition functions and graph polynomials

This page was built for publication:

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