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

DOI10.1051/RO/2015017zbMATH Open1357.68207OpenAlexW2305237467MaRDI QIDQ2805480FDOQ2805480

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

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

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)

Cites Work

• A Sufficient Condition for Backtrack-Free Search
• Principles and Practice of Constraint Programming – CP 2004
• Decomposing constraint satisfaction problems using database techniques
• A comparison of structural CSP decomposition methods
• Partition search for non-binary constraint satisfaction
• Generalized hypertree decompositions: NP-hardness and tractable variants
• Constraint solving via fractional edge covers
• Graph minors. II. Algorithmic aspects of tree-width
• STR2: optimized simple tabular reduction for table constraints
• Hypertree decompositions and tractable queries
• 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
• Networks of constraints: Fundamental properties and applications to picture processing
• Tree clustering for constraint networks
• Constructing optimal binary decision trees is NP-complete
• A sufficient condition for backtrack-bounded search
• Robbers, marshals, and guards: Game theoretic and logical characterizations of hypertree width.
• Hypertree-width and related hypergraph invariants
• Title not available (Why is that?)
• Hybrid backtracking bounded by tree-decomposition of constraint networks
• A backtracking-based algorithm for hypertree decomposition

Cited In (1)

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

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)