Artículos de revistas
A LINEAR-TIME ALGORITHM FOR PROPER INTERVAL GRAPH RECOGNITION
Registro en:
Information Processing Letters. Elsevier Science Bv, v. 56, n. 3, n. 179, n. 184, 1995.
0020-0190
WOS:A1995TE02500010
10.1016/0020-0190(95)00133-W
Autor
DEFIGUEIREDO, CMH
MEIDANIS, J
DEMELLO, CP
Institución
Resumen
Interval graphs are the intersection graphs of families of intervals in the real line. If the intervals can be chosen so that no interval contains another, we obtain the subclass of proper interval graphs. We show how to recognize proper interval graphs in linear time by constructing the clique partition from the output of a single lexicographic breadth-first search. 56 3 179 184