An optimal k-consistency algorithm

DOI10.1016/0004-3702(89)90080-5MaRDI QIDQ1124348zbMATHOpenAlexFDO

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

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)

Recommendations

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

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

Cited in

(41)

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

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)