Tractable hypergraph properties for constraint satisfaction and conjunctive queries
From MaRDI portal
Publication:2875201
DOI10.1145/1806689.1806790zbMath1293.68171OpenAlexW2159738186MaRDI QIDQ2875201
Publication date: 13 August 2014
Published in: Proceedings of the forty-second ACM symposium on Theory of computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/1806689.1806790
Related Items (14)
Tractable counting of the answers to conjunctive queries ⋮ The complexity of weighted counting for acyclic conjunctive queries ⋮ Enumerating homomorphisms ⋮ The power of propagation: when GAC is enough ⋮ Computing hypergraph width measures exactly ⋮ Quantum hypergraph states ⋮ On the complexity of existential positive queries ⋮ Decomposing Quantified Conjunctive (or Disjunctive) Formulas ⋮ Unnamed Item ⋮ Characterizing tractability of simple well-designed pattern trees with projection ⋮ Characterising the complexity of constraint satisfaction problems defined by 2-constraint forbidden patterns ⋮ Unnamed Item ⋮ Structural tractability of enumerating CSP solutions ⋮ Constructing NP-intermediate problems by blowing holes with parameters of various properties
This page was built for publication: Tractable hypergraph properties for constraint satisfaction and conjunctive queries