Catalogue of Artificial Intelligence Techniques


Jump to: Top | Entry | References | Comments

View Maths as: Images | MathML

Maximum Cardinality Search

Keywords: adaptive consistency

Categories: Inference and Reasoning , Problem Solving

Author(s): Rina Dechter

A method of ordering nodes in a graph which, whenever possible, guarantees the following condition: no two nodes will be linked to a successor node unless the two are linked together. The ordering consists of sequentially selecting a node that makes the largest number of connections with those selected earlier. This search yields close to optimal orderings for conducting adaptive consistency. It is also used in Constraint Satisfaction and probabilistic reasoning problems to transform a network into a tree of clusters, thus facilitating local propagation and relaxation.



Add Comment

No comments.