Tractability beyond \(\beta\)-acyclicity for conjunctive queries with negation and SAT
From MaRDI portal
Publication:2110380
DOI10.1016/j.tcs.2022.12.002OpenAlexW4313340638MaRDI QIDQ2110380
Publication date: 21 December 2022
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2007.08876
Cites Work
- Satisfiability of acyclic and almost acyclic CNF formulas
- Some characterizations of \(\gamma \) and \(\beta \)-acyclicity of hypergraphs
- Hypertree decompositions and tractable queries
- Decomposing constraint satisfaction problems using database techniques
- Upper bounds to the clique width of graphs
- Hypertree width and related hypergraph invariants
- Size Bounds and Query Plans for Relational Joins
- Degrees of acyclicity for hypergraphs and relational database schemes
- Hypergraph Acyclicity and Propositional Model Counting
- Solving #SAT and MAXSAT by Dynamic Programming
- The complexity of homomorphism and constraint satisfaction problems seen from the other side
- Constraint solving via fractional edge covers
- Node-Deletion Problems on Bipartite Graphs
- Reducibility among Combinatorial Problems
- Tractable Hypergraph Properties for Constraint Satisfaction and Conjunctive Queries
- Parameterized Algorithms
- A Computing Procedure for Quantification Theory
- Point-Width and Max-CSPs
- Hardness of computing width parameters based on branch decompositions over the vertex set
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: Tractability beyond \(\beta\)-acyclicity for conjunctive queries with negation and SAT
