= Maximum cardinality search
<Maximum cardinality search> is a <graph> search in which an unselected <vertex>'s score counts its already selected <graph neighbours>. Repeatedly select a <vertex> of maximum score, breaking ties arbitrarily, and update its unselected <graph neighbours>. On a <chordal graph>, the reverse selection order is a <perfect elimination ordering>. On $C_4$, selecting $(a,b,c,d)$ instead yields candidate deletion order $(d,c,b,a)$; $d$'s later <graph neighbours> $a,c$ are not adjacent, so the <clique> check fails.<Chordal Graphs and Semidefinite Optimization by Lieven Vandenberghe and others>[§4.2; Algorithm 4.2]{ref}
Back to article page
