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:
“I have no purpose to introduce political and social equality between the white and black races. There is a physical difference between the two, which, in my judgement, will probably for ever forbid their living together upon the footing of perfect equality; and inasmuch as it becomes a necessity that there must be a difference, I ... am in favour of the race to which I belong having the superior position.”
—Abraham Lincoln (1809–1865)
“The kind of Unitarian
Who having by elimination got
From many gods to Three, and Three to One,
Thinks why not taper off to none at all.”
—Robert Frost (1874–1963)
“An efficient and valuable man does what he can, whether the community pay him for it or not. The inefficient offer their inefficiency to the highest bidder, and are forever expecting to be put into office. One would suppose that they were rarely disappointed.”
—Henry David Thoreau (1817–1862)
“While you are nurturing your newborn, you need someone to nurture you, whether it is with healthful drinks while you’re nursing, or with words of recognition and encouragement as you talk about your feelings. In this state of continual giving to your infant—whether it is nourishment or care or love—you are easily drained, and you need to be replenished from sources outside yourself so that you will have reserves to draw from.”
—Sally Placksin (20th century)