New schemes for simplifying binary constraint satisfaction problems

DOI10.23638/DMTCS-22-1-10MaRDI QIDQ3386610zbMATH OpenOpenAlexFDO

Authors Wady Naanaa

Publication date 5 January 2021

Full work available at URL https://hal.archives-ouvertes.fr/hal-01731250

zbMATH Keywords

constraint satisfaction problemstractable CSPvalue mergingvariable elimination

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Parameterized complexity, tractability and kernelization (68Q27) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Recommendations

• Variable Elimination in Binary CSPs
• Variable and value elimination in binary constraint satisfaction via forbidden patterns
• Characterising tractable constraints
• scientific article; zbMATH DE number 1008453
• scientific article; zbMATH DE number 1234562

Cited in

(11)

• Fundamental properties of neighbourhood substitution in constraint satisfaction problems
• Binary constraint satisfaction problems defined by excluded topological minors
• A new branch-and-filter exact algorithm for binary constraint satisfaction problems
• Variable and value elimination in binary constraint satisfaction via forbidden patterns
• Broken triangles: from value merging to a tractable class of general-arity constraint satisfaction problems
• Fast reductions from RAMs to delegatable succinct constraint satisfaction problems
• Extremal CSPs
• scientific article; zbMATH DE number 1231545 (Why is no real title available?)
• Bit-vector algorithms for binary constraint satisfaction and subgraph isomorphism
• Logic for Programming, Artificial Intelligence, and Reasoning
• Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems

This page was built for publication: New schemes for simplifying binary constraint satisfaction problems

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