Characterising tractable constraints
From MaRDI portal
Publication:1321064
DOI10.1016/0004-3702(94)90021-3zbMath0803.68053OpenAlexW1748315421MaRDI QIDQ1321064
Martin C. Cooper, Peter G. Jeavons, David A. Cohen
Publication date: 3 May 1994
Published in: Artificial Intelligence (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0004-3702(94)90021-3
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)
Related Items
Reduction operations in fuzzy or valued constraint satisfaction, Tractability in constraint satisfaction problems: a survey, On Singleton Arc Consistency for CSPs Defined by Monotone Patterns, Local and global relational consistency, Uncovering trees in constraint networks, Unnamed Item, An algebraic characterization of tractable constraints, CSP beyond tractable constraint languages, A hybrid tractable class for non-binary CSPs, Placement Inference for a Client-Server Calculus, Colouring, constraint satisfaction, and complexity, Learnability of quantified formulas., Hybrid Tractable Classes of Constraint Problems, The complexity of soft constraint satisfaction, On singleton arc consistency for CSPs defined by monotone patterns, Constraint satisfaction -- algorithms and complexity analysis, A new tractable class of constraint satisfaction problems, Generalizing constraint satisfaction on trees: hybrid tractability and variable elimination, Parameterized Complexity Results in Symmetry Breaking, Parameterized Complexity of the Workflow Satisfiability Problem, Tractable constraints on ordered domains, Robust Algorithms with Polynomial Loss for Near-Unanimity CSPs, Tractable constraints on ordered domains, Galois connections for patterns: an algebra of labelled graphs, Half-integrality, LP-branching, and FPT Algorithms, Constraints, consistency and closure, On the algebraic structure of combinatorial problems, Dualities for Constraint Satisfaction Problems, Characterising the complexity of constraint satisfaction problems defined by 2-constraint forbidden patterns, Periodic constraint satisfaction problems: Tractable subclasses
Cites Work
- Unnamed Item
- Comments on Mohr and Henderson's path consistency algorithm
- Network-based heuristics for constraint-satisfaction problems
- An optimal k-consistency algorithm
- From local to global consistency
- A generic arc-consistency algorithm and its specializations
- Consistency in networks of relations
- Fast parallel constraint satisfaction
- Decomposing constraint satisfaction problems using database techniques
- Networks of constraints: Fundamental properties and applications to picture processing
- Constraint relaxation may be perfect
- A sufficient condition for backtrack-bounded search
- A Sufficient Condition for Backtrack-Free Search
