An optimal k-consistency algorithm

DOI10.1016/0004-3702(89)90080-5zbMath0678.68058OpenAlexW2057872609MaRDI QIDQ1124348

Martin C. Cooper

Publication date: 1989

Published in: Artificial Intelligence (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0004-3702(89)90080-5

zbMATH Keywords

arc-consistency algorithmconsistent labeling problemk-consistency algorithmpath-consistency algorithm

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Algorithms in computer science (68W99)

Related Items

Reduction operations in fuzzy or valued constraint satisfaction ⋮ Model-based inference in CHARME. ⋮ Binary constraint satisfaction problems defined by excluded topological minors ⋮ Decision-support with preference constraints ⋮ Theoretical analysis of singleton arc consistency and its extensions ⋮ Representing and solving finite-domain constraint problems using systems of polynomials ⋮ Revisiting global constraint satisfaction ⋮ From local to global consistency in temporal constraint networks ⋮ Local and global relational consistency ⋮ Fundamental properties of neighbourhood substitution in constraint satisfaction problems ⋮ A multiagent evolutionary algorithm with direct and indirect combined representation for constraint satisfaction problems ⋮ Mixed logical-linear programming ⋮ Generalising submodularity and Horn clauses: Tractable optimization problems defined by tournament pair multimorphisms ⋮ Constraint satisfaction -- algorithms and complexity analysis ⋮ From local to global consistency ⋮ Argumentation frameworks as constraint satisfaction problems ⋮ Combinatorial problems raised from 2-semilattices ⋮ A polynomial relational class of binary CSP ⋮ Multi-agent oriented constraint satisfaction ⋮ Tractable disjunctions of linear constraints: Basic results and applications to temporal reasoning ⋮ On m-Junctive Predicates on a Finite Set ⋮ Tractable combinations of theories via sampling ⋮ Constraints, consistency and closure ⋮ Constraint propagation techniques for the disjunctive scheduling problem ⋮ A Logical Approach to Constraint Satisfaction ⋮ Unnamed Item ⋮ Backjump-based backtracking for constraint satisfaction problems ⋮ Characterising tractable constraints ⋮ Cyclic consistency: A local reduction operation for binary valued constraints ⋮ High-order consistency in valued constraint satisfaction

Cites Work

• Comments on Mohr and Henderson's path consistency algorithm
• Consistency in networks of relations
• Networks of constraints: Fundamental properties and applications to picture processing
• Synthesizing constraint expressions