Efficient Recognition Algorithms
Determining whether a given graph G = (V, E) is an interval graph can be done in O(|V|+|E|) time by seeking an ordering of the maximal cliques of G that is consecutive with respect to vertex inclusion.
The original linear time recognition algorithm of Booth & Lueker (1976) is based on their complex PQ tree data structure, but Habib et al. (2000) showed how to solve the problem more simply using lexicographic breadth-first search, based on the fact that a graph is an interval graph if and only if it is chordal and its complement is a comparability graph.
Read more about this topic: Interval Graph
Famous quotes containing the words efficient and/or recognition:
“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)
“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)