Tractable Hypergraph Properties for Constraint Satisfaction and Conjunctive Queries
From MaRDI portal
Publication:5395737
DOI10.1145/2535926zbMath1281.68135OpenAlexW2143238590MaRDI QIDQ5395737
Publication date: 17 February 2014
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/2535926
Analysis of algorithms and problem complexity (68Q25) Hypergraphs (05C65) Graph theory (including graph drawing) in computer science (68R10) Combinatorial optimization (90C27)
Related Items
Tractability in constraint satisfaction problems: a survey ⋮ Structural decompositions for problems with global constraints ⋮ The Complexity of General-Valued CSPs ⋮ The Power of Local Consistency in Conjunctive Queries and Constraint Satisfaction Problems ⋮ Binary constraint satisfaction problems defined by excluded topological minors ⋮ Unnamed Item ⋮ It's all a matter of degree. Using degree information to optimize multiway joins ⋮ Regularizing conjunctive features for classification ⋮ Towards a characterization of constant-factor approximable finite-valued CSPs ⋮ Tree projections and structural decomposition methods: minimality and game-theoretic characterization ⋮ Unnamed Item ⋮ On the non-efficient PAC learnability of conjunctive queries ⋮ Parameterized Counting and Cayley Graph Expanders ⋮ The Complexity of Valued CSPs ⋮ Fractional Edge Cover Number of Model RB ⋮ Tree projections and constraint optimization problems: fixed-parameter tractability and parallel algorithms ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Greedy strategies and larger islands of tractability for conjunctive queries and constraint satisfaction problems ⋮ Fast and parallel decomposition of constraint satisfaction problems ⋮ The Power of Linear Programming for General-Valued CSPs ⋮ Tractability beyond \(\beta\)-acyclicity for conjunctive queries with negation and SAT ⋮ The Complexity of General-Valued Constraint Satisfaction Problems Seen from the Other Side ⋮ Broken triangles: from value merging to a tractable class of general-arity constraint satisfaction problems
This page was built for publication: Tractable Hypergraph Properties for Constraint Satisfaction and Conjunctive Queries
