Polynomial constraint satisfaction problems, graph bisection, and the Ising partition function
DOI10.1145/1597036.1597049zbMath1298.68256arXivcs/0604079MaRDI QIDQ2930272
Gregory B. Sorkin, Alexander D. Scott
Publication date: 18 November 2014
Published in: ACM Transactions on Algorithms (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/cs/0604079
partition function; generating function; discrete optimization; constraint satisfaction; exact algorithm; exponential-time algorithm
68Q25: Analysis of algorithms and problem complexity
05C70: Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
68T20: Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
05C85: Graph algorithms (graph-theoretic aspects)
