Catalogue of Artificial Intelligence Techniques
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.
- 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.