An algebraic characterization of tractable constraints

DOI10.1007/bfb0030886zbMath1527.68213OpenAlexW1549495856MaRDI QIDQ6085763

David A. Cohen, Peter G. Jeavons

Publication date: 12 December 2023

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bfb0030886

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Network-based heuristics for constraint-satisfaction problems
• A generic arc-consistency algorithm and its specializations
• Structure identification in relational data
• Consistency in networks of relations
• Fast parallel constraint satisfaction
• Decomposing constraint satisfaction problems using database techniques
• Characterising tractable constraints
• Networks of constraints: Fundamental properties and applications to picture processing
• Constraint relaxation may be perfect
• Closed systems of functions and predicates
• A sufficient condition for backtrack-bounded search
• On binary constraint problems
• The complexity of satisfiability problems
• The Two-Valued Iterative Systems of Mathematical Logic. (AM-5)
• Tractable constraints on ordered domains