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 v, v and the neighbors of v that occur after v in the order form a clique. A graph is chordal if and only if it has a perfect elimination ordering (Fulkerson & Gross 1965).
Rose, Lueker & Tarjan (1976) (see also Habib et al. 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 v from the earliest set in the sequence that contains previously unchosen vertices, and splits each set S of the sequence into two smaller subsets, the first consisting of the neighbors of v in 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 (Bodlaender, Fellows & Warnow 1992), whereas the probe graph problem on chordal graphs has polynomial-time complexity (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; Chandran et al. (2003) use this connection to antimatroids as part of an algorithm for efficiently listing all perfect elimination orderings of a given chordal graph.
Read more about this topic: Chordal Graph
Famous quotes containing the words perfect, elimination, efficient and/or recognition:
“When I, sitting, heard the astronomer, where he lectured with such applause in the lecture room,
How soon, unaccountable, I became tired and sick;
Till rising and gliding out, I wander’d off by myself,
In the mystical moist night-air, and from time to time,
Look’d up in perfect silence at the stars.”
—Walt Whitman (1819–1892)
“To reduce the imagination to a state of slavery—even though it would mean the elimination of what is commonly called happiness—is to betray all sense of absolute justice within oneself. Imagination alone offers me some intimation of what can be.”
—André Breton (1896–1966)
“I make no secret of the fact that I would rather lie on a sofa than sweep beneath it. But you have to be efficient if you’re going to be lazy.”
—Shirley Conran (b. 1932)
“Art is the imposing of a pattern on experience, and our aesthetic enjoyment is recognition of the pattern.”
—Alfred North Whitehead (1861–1947)