Acyclic orders, partition schemes and CSPs: unified hardness proofs and improved algorithms
From MaRDI portal
Publication:2238592
DOI10.1016/j.artint.2021.103505OpenAlexW3155946679WikidataQ113879646 ScholiaQ113879646MaRDI QIDQ2238592
Victor Lagerkvist, Peter Jonsson, George Osipov
Publication date: 2 November 2021
Published in: Artificial Intelligence (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.artint.2021.103505
Related Items (2)
Solving infinite-domain CSPs using the patchwork property ⋮ Computational Short Cuts in Infinite Domain Constraint Satisfaction
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Maintaining knowledge about temporal intervals
- Strong partial clones and the time complexity of SAT problems
- An initial study of time complexity in infinite-domain constraint satisfaction
- Correlation clustering
- On the complexity of qualitative spatial reasoning: A maximal tractable fragment of the Region Connection Calculus
- Satisfiability problems on intervals and unit intervals
- Relation algebras and their application in temporal and spatial reasoning
- Datalog and constraint satisfaction with infinite templates
- Relation algebras of intervals
- A Model-Theoretic View on Qualitative Constraint Reasoning
- Subexponential Algorithms for Unique Games and Related Problems
- Reasoning about temporal relations
- Handbook of Spatial Logics
- The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
- Complexity and algorithms for reasoning about time
- Parameterized complexity: exponential speed-up for planar graph problems
- Sparsification of SAT and CSP Problems via Tractable Extensions
- A Proof of the CSP Dichotomy Conjecture
- On the Subexponential-Time Complexity of CSP
- Optimal Sparsification for Some Binary CSPs Using Low-Degree Polynomials
- On the complexity of \(k\)-SAT
This page was built for publication: Acyclic orders, partition schemes and CSPs: unified hardness proofs and improved algorithms
