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:
“The truly efficient laborer will not crowd his day with work, but will saunter to his task, surrounded by a wide halo of ease and leisure, and then do but what he loves best. He is anxious only about the fruitful kernels of time.”
—Henry David Thoreau (1817–1862)
“Design in art, is a recognition of the relation between various things, various elements in the creative flux. You can’t invent a design. You recognise it, in the fourth dimension. That is, with your blood and your bones, as well as with your eyes.”
—D.H. (David Herbert)