Automata, Languages and Programming

DOI10.1007/B99859zbMath1098.68616OpenAlexW2505584480MaRDI QIDQ5466470

Martin Grohe, Andrei A. Bulatov

Publication date: 24 August 2005

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/b99859

zbMATH Keywords

partition functiongraph homomorphismconstraint satisfactioncounting complexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Classical equilibrium statistical mechanics (general) (82B05) Coloring of graphs and hypergraphs (05C15) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Related Items (9)

Perfect matchings, rank of connection tensors and graph homomorphisms ⋮ Towards a dichotomy theorem for the counting constraint satisfaction problem ⋮ The complexity of complex weighted Boolean \#CSP ⋮ From Holant to \#CSP and back: dichotomy for Holant\(^{c}\) problems ⋮ Path coupling using stopping times and counting independent sets and colorings in hypergraphs ⋮ Holographic Algorithms with Matchgates Capture Precisely Tractable Planar #CSP ⋮ Zero-free regions of partition functions with applications to algorithms and graph limits ⋮ Classical simulation of quantum circuits by half Gauss sums ⋮ A dichotomy for real weighted Holant problems

This page was built for publication: Automata, Languages and Programming