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)
“By now, legions of tireless essayists and op-ed columnists have dressed feminists down for making such a fuss about entering the professions and earning equal pay that everyone’s attention has been distracted from the important contributions of mothers working at home. This judgment presumes, of course, that prior to the resurgence of feminism in the ‘70s, housewives and mothers enjoyed wide recognition and honor. This was not exactly the case.”
—Mary Kay Blakely (20th century)