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:
“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)
“Productive collaborations between family and school, therefore, will demand that parents and teachers recognize the critical importance of each other’s participation in the life of the child. This mutuality of knowledge, understanding, and empathy comes not only with a recognition of the child as the central purpose for the collaboration but also with a recognition of the need to maintain roles and relationships with children that are comprehensive, dynamic, and differentiated.”
—Sara Lawrence Lightfoot (20th century)