Fast and parallel decomposition of constraint satisfaction problems

DOI10.1007/s10601-022-09332-1OpenAlexW4281718597MaRDI QIDQ2079275

Reinhard Pichler, Georg Gottlob, Cem Okulmus

Publication date: 29 September 2022

Published in: Constraints (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10601-022-09332-1

zbMATH Keywords

parallel computinghypergraphsconstraint satisfactionstructural decomposition methods

Mathematics Subject Classification ID

Artificial intelligence (68Txx) Theory of data (68Pxx) Theory of computing (68Qxx)

Related Items

Computing optimal hypertree decompositions with SAT

Uses Software

• Algorithm 97
• EmptyHeaded
• HyperBench

Cites Work

• Hypertree decompositions and tractable queries
• A unified theory of structural tractability for constraint satisfaction problems
• Decomposing constraint satisfaction problems using database techniques
• Treewidth. Computations and approximations
• A comparison of structural CSP decomposition methods
• Conjunctive-query containment and constraint satisfaction
• Hypertree width and related hypergraph invariants
• Degrees of acyclicity for hypergraphs and relational database schemes
• Generalized hypertree decompositions: NP-hardness and tractable variants
• Constraint solving via fractional edge covers
• Graph minors. II. Algorithmic aspects of tree-width
• Communicating sequential processes
• A compressed Generalized Hypertree Decomposition-based solving technique for non-binary Constraint Satisfaction Problems
• Term Rewriting and All That
• HyperBench
• Computing Optimal Hypertree Decompositions
• Tractable Hypergraph Properties for Constraint Satisfaction and Conjunctive Queries
• A backtracking-based algorithm for hypertree decomposition
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• A Theorem on Boolean Matrices
• The PACE 2019 Parameterized Algorithms and Computational Experiments Challenge: The Fourth Iteration (Invited Paper)