Constraint solving via fractional edge covers

DOI10.1145/1109557.1109590zbMath1192.68642arXiv1711.04506MaRDI QIDQ3581534

Dániel Marx, Martin Grohe

Publication date: 16 August 2010

Published in: ACM Transactions on Algorithms, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm - SODA '06 (Search for Journal in Brave)

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

zbMATH Keywords

hypergraphs; constraint satisfaction; hypertree width; fractional edge covers

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

05C65: Hypergraphs

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.)

05C85: Graph algorithms (graph-theoretic aspects)