An optimal k-consistency algorithm

DOI10.1016/0004-3702(89)90080-5zbMATH Open0678.68058OpenAlexW2057872609MaRDI QIDQ1124348FDOQ1124348

Authors: M. 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

Recommendations

• A generic arc-consistency algorithm and its specializations
• scientific article; zbMATH DE number 2080326
• Arc consistency revisited
• scientific article
• Constraints, consistency and closure

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)

Cites Work

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

Cited In (39)

• Constraint propagation techniques for the disjunctive scheduling problem
• Theoretical analysis of singleton arc consistency and its extensions
• Local and global relational consistency
• From local to global consistency in temporal constraint networks
• A Logical Approach to Constraint Satisfaction
• The Consistent Labeling Problem: Part II
• Title not available (Why is that?)
• Decision-support with preference constraints
• Multiconsistency and robustness with global constraints
• Fundamental properties of neighbourhood substitution in constraint satisfaction problems
• Arc consistency for factorable relations.
• A polynomial relational class of binary CSP
• Binary constraint satisfaction problems defined by excluded topological minors
• From local to global consistency
• Revisiting global constraint satisfaction
• Constraints, consistency and closure
• Characterising tractable constraints
• Multiconsistency and Robustness with Global Constraints
• Second-order consistencies
• Tractable disjunctions of linear constraints: Basic results and applications to temporal reasoning
• High-order consistency in valued constraint satisfaction
• Title not available (Why is that?)
• Multi-agent oriented constraint satisfaction
• Tractable combinations of theories via sampling
• Mixed logical-linear programming
• An optimal coarse-grained arc consistency algorithm
• Combinatorial problems raised from 2-semilattices
• Reduction operations in fuzzy or valued constraint satisfaction
• Model-based inference in CHARME.
• Representing and solving finite-domain constraint problems using systems of polynomials
• On m-Junctive Predicates on a Finite Set
• Generalising submodularity and Horn clauses: Tractable optimization problems defined by tournament pair multimorphisms
• Path Consistency by Dual Consistency
• Backjump-based backtracking for constraint satisfaction problems
• A multiagent evolutionary algorithm with direct and indirect combined representation for constraint satisfaction problems
• Argumentation frameworks as constraint satisfaction problems
• On the Power of k-Consistency
• Cyclic consistency: A local reduction operation for binary valued constraints
• Constraint satisfaction -- algorithms and complexity analysis

This page was built for publication: An optimal k-consistency algorithm

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