Computing optimal hypertree decompositions with SAT

DOI10.1016/j.artint.2023.104015OpenAlexW4386827690MaRDI QIDQ6067037

André Schidler, Stefan Szeider

Publication date: 14 December 2023

Published in: Artificial Intelligence (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.artint.2023.104015

zbMATH Keywords

optimizationconstraint programminghypertree widthSATSAT encodingSMTMaxSAT

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Hypergraphs (05C65) Graph theory (including graph drawing) in computer science (68R10) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Cites Work

• Fundamentals of parameterized complexity
• Hypertree decompositions and tractable queries
• Robbers, marshals, and guards: Game theoretic and logical characterizations of hypertree width.
• MiniCon: a scalable algorithm for answering queries using views
• PySAT: a Python toolkit for prototyping with SAT oracles
• SAT-encodings for special treewidth and pathwidth
• Fast and parallel decomposition of constraint satisfaction problems
• \textsc{OptiMathSAT}: a tool for optimization modulo theories
• Abstract cores in implicit hitting set MaxSat solving
• A Survey of Satisfiability Modulo Theory
• A SAT Approach to Clique-Width
• Towards an Optimal CNF Encoding of Boolean Cardinality Constraints
• Constraint solving via fractional edge covers
• Encoding Treewidth into SAT
• Jdrasil: A Modular Library for Computing Tree Decompositions
• Solving Graph Problems via Potential Maximal Cliques
• HyperBench
• Computing Optimal Hypertree Decompositions
• SAT-Encodings for Treecut Width and Treedepth
• A backtracking-based algorithm for hypertree decomposition
• SOFSEM 2005: Theory and Practice of Computer Science
• The PACE 2019 Parameterized Algorithms and Computational Experiments Challenge: The Fourth Iteration (Invited Paper)
• Principles and Practice of Constraint Programming – CP 2003
• Graph-Theoretic Concepts in Computer Science

This page was built for publication: Computing optimal hypertree decompositions with SAT