The complexity of counting colourings and independent sets in sparse graphs and hypergraphs
From MaRDI portal
Publication:1590082
DOI10.1007/PL00001601zbMath0963.68082MaRDI QIDQ1590082
Publication date: 19 December 2000
Published in: Computational Complexity (Search for Journal in Brave)
68Q25: Analysis of algorithms and problem complexity
68R10: Graph theory (including graph drawing) in computer science
05C15: Coloring of graphs and hypergraphs
Related Items
Algorithms for four variants of the exact satisfiability problem, The complexity of weighted Boolean \#CSP with mixed signs, Towards a dichotomy theorem for the counting constraint satisfaction problem, Holographic reduction, interpolation and hardness, Computational complexity of counting problems on 3-regular planar graphs, Improved inapproximability results for counting independent sets in the hard-core model, Counting Maximal Independent Sets in Subcubic Graphs