# Catalogue of Artificial Intelligence Techniques

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.

### References:

- Tarjan, R.E. and Yannakakis, M.,
*Simple linear-time algorithms to test chordality of graphs, test acyclicity of hypergraphs and selectively reduce acyclic hypergraphs*SIAM J. Computing**13**(1984), 566--579.

### Comments:

No comments.