A LINEAR-TIME ALGORITHM FOR PROPER INTERVAL GRAPH RECOGNITION

dc.creatorDEFIGUEIREDO, CMH
dc.creatorMEIDANIS, J
dc.creatorDEMELLO, CP
dc.date1995
dc.date40483
dc.date2014-12-16T11:32:58Z
dc.date2015-11-26T17:52:09Z
dc.date2014-12-16T11:32:58Z
dc.date2015-11-26T17:52:09Z
dc.date.accessioned2018-03-29T00:35:36Z
dc.date.available2018-03-29T00:35:36Z
dc.identifierInformation Processing Letters. Elsevier Science Bv, v. 56, n. 3, n. 179, n. 184, 1995.
dc.identifier0020-0190
dc.identifierWOS:A1995TE02500010
dc.identifier10.1016/0020-0190(95)00133-W
dc.identifierhttp://www.repositorio.unicamp.br/jspui/handle/REPOSIP/76013
dc.identifierhttp://www.repositorio.unicamp.br/handle/REPOSIP/76013
dc.identifierhttp://repositorio.unicamp.br/jspui/handle/REPOSIP/76013
dc.identifier.urihttp://repositorioslatinoamericanos.uchile.cl/handle/2250/1290165
dc.descriptionInterval 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.
dc.description56
dc.description3
dc.description179
dc.description184
dc.languageen
dc.publisherElsevier Science Bv
dc.publisherAmsterdam
dc.publisherHolanda
dc.relationInformation Processing Letters
dc.relationInf. Process. Lett.
dc.rightsfechado
dc.rightshttp://www.elsevier.com/about/open-access/open-access-policies/article-posting-policy
dc.sourceWeb of Science
dc.subjectDESIGN OF ALGORITHMS
dc.subjectINTERVAL GRAPHS
dc.subjectINDIFFERENCE GRAPHS
dc.titleA LINEAR-TIME ALGORITHM FOR PROPER INTERVAL GRAPH RECOGNITION
dc.typeArtículos de revistas


Este ítem pertenece a la siguiente institución