Please use this identifier to cite or link to this item: http://repositorio.unicamp.br/jspui/handle/REPOSIP/76013
Type: Artigo de periódico
Title: A LINEAR-TIME ALGORITHM FOR PROPER INTERVAL GRAPH RECOGNITION
Author: DEFIGUEIREDO, CMH
MEIDANIS, J
DEMELLO, CP
Abstract: 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.
Subject: DESIGN OF ALGORITHMS
INTERVAL GRAPHS
INDIFFERENCE GRAPHS
Country: Holanda
Editor: Elsevier Science Bv
Rights: fechado
Identifier DOI: 10.1016/0020-0190(95)00133-W
Date Issue: 1995
Appears in Collections:Unicamp - Artigos e Outros Documentos

Files in This Item:
File Description SizeFormat 
WOSA1995TE02500010.pdf529.12 kBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.