Generalized hypertree decomposition for solving non binary CSP with compressed table constraints

DOI10.1051/RO/2015017MaRDI QIDQ2805480zbMATH OpenOpenAlexFDO

Authors Zineb Habbas, Kamal Amroun, D. J. Singer

Publication date 11 May 2016

Published in RAIRO. Operations Research (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1051/ro/2015017

zbMATH Keywords

constraint satisfaction problemscompressed table constraintsgeneralized hypertree decomposition

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Recommendations

• A compressed generalized hypertree decomposition-based solving technique for non-binary constraint satisfaction problems
• A comparison of structural CSP decomposition methods
• Beyond Hypertree Width: Decomposition Methods Without Decompositions
• Hyperconsistency width for constraint satisfaction: Algorithms and complexity results
• Decomposable constraints

Cites work

• scientific article; zbMATH DE number 1423226 (Why is no real title available?)
• A Sufficient Condition for Backtrack-Free Search
• A backtracking-based algorithm for hypertree decomposition
• A comparison of structural CSP decomposition methods
• A sufficient condition for backtrack-bounded search
• A unified theory of structural tractability for constraint satisfaction problems
• An MDD-based generalized arc consistency algorithm for positive and negative table constraints and some global constraints
• Constructing optimal binary decision trees is NP-complete
• Decomposing constraint satisfaction problems using database techniques
• Generalized hypertree decompositions: NP-hardness and tractable variants
• Graph minors. II. Algorithmic aspects of tree-width
• Hybrid backtracking bounded by tree-decomposition of constraint networks
• Hypertree decompositions and tractable queries
• Hypertree-width and related hypergraph invariants
• Networks of constraints: Fundamental properties and applications to picture processing
• Partition search for non-binary constraint satisfaction
• Principles and Practice of Constraint Programming – CP 2004
• Robbers, marshals, and guards: Game theoretic and logical characterizations of hypertree width.
• STR2: optimized simple tabular reduction for table constraints
• Tree clustering for constraint networks

Cited in

(1)

• A compressed generalized hypertree decomposition-based solving technique for non-binary constraint satisfaction problems

Describes a project that uses

Uses Software

• STR2

This page was built for publication: Generalized hypertree decomposition for solving non binary CSP with compressed table constraints

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2805480)