Editing Chordal graph (section)

==Perfect elimination and efficient recognition==
A ''perfect elimination ordering'' in a graph is an ordering of the vertices of the graph such that, for each vertex {{mvar|v}}, {{mvar|v}} and the [[Neighborhood (graph theory)|neighbors]] of {{mvar|v}} that occur after {{mvar|v}} in the order form a [[Clique (graph theory)|clique]]. A graph is chordal [[if and only if]] it has a perfect elimination ordering.{{sfnp|Rose|1970}}

{{harvtxt|Rose|Lueker|Tarjan|1976}} (see also {{harvnb|Habib|McConnell|Paul|Viennot|2000}}) show that a perfect elimination ordering of a chordal graph may be found efficiently using an algorithm known as [[lexicographic breadth-first search]]. This algorithm maintains a partition of the vertices of the graph into a sequence of sets; initially this sequence consists of a single set with all vertices. The algorithm repeatedly chooses a vertex {{mvar|v}} from the earliest set in the sequence that contains previously unchosen vertices, and splits each set {{mvar|S}} of the sequence into two smaller subsets, the first consisting of the neighbors of {{mvar|v}} in {{mvar|S}} and the second consisting of the non-neighbors. When this splitting process has been performed for all vertices, the sequence of sets has one vertex per set, in the reverse of a perfect elimination ordering.

Since both this lexicographic breadth first search process and the process of testing whether an ordering is a perfect elimination ordering can be performed in [[linear time]], it is possible to recognize chordal graphs in linear time.  The [[graph sandwich problem]] on chordal graphs is [[NP-complete]]{{sfnp|Bodlaender|Fellows|Warnow|1992}} whereas the probe graph problem on chordal graphs has polynomial-time complexity.{{sfnp|Berry|Golumbic|Lipshteyn|2007}}

The set of all perfect elimination orderings of a chordal graph can be modeled as the ''basic words'' of an [[antimatroid]]; {{harvtxt|Chandran|Ibarra|Ruskey|Sawada|2003}} use this connection to antimatroids as part of an algorithm for efficiently listing all perfect elimination orderings of a given chordal graph.