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:
“As machines become more and more efficient and perfect, so it will become clear that imperfection is the greatness of man.”
—Ernst Fischer (1899–1972)
“The person who designed a robot that could act and think as well as your four-year-old would deserve a Nobel Prize. But there is no public recognition for bringing up several truly human beings.”
—C. John Sommerville (20th century)