Please use this identifier to cite or link to this item: http://hdl.handle.net/11422/1497
Full metadata record
DC FieldValueLanguage
dc.contributor.authorSzwarcfiter, Jayme Luiz-
dc.contributor.authorBornstein, Claudson Ferreira-
dc.date.accessioned2017-03-06T13:10:40Z-
dc.date.available2017-03-08T03:00:13Z-
dc.date.issued1991-12-31-
dc.identifier.citationSZWARCFITER, J. L. Clique graphs of chordal and path graphs. Rio de Janeiro: NCE, UFRJ, 1991. 11 p. (Relatório Técnico, 23/91)pt_BR
dc.identifier.urihttp://hdl.handle.net/11422/1497-
dc.description.abstractWe characterize clique graphs of chordal and path graphs. A special class of graphs called expanded trees is introduced. They form a subclass of disk-Helly graphs. It is shown that the clique graph of every chordal (hence path) graph is an expanded tree. In addition, every expanded tree is the clique graph of some path (hence chordal) graph. Different characterizations of expanded trees are described, leading to a polynomial time algorithm for recognizing clique graphs of chordal and path graphs.en
dc.languageengpt_BR
dc.relation.ispartofRelatório Técnico NCEpt_BR
dc.rightsAcesso Abertopt_BR
dc.subjectGrafos cordalpt_BR
dc.subjectAlgoritmospt_BR
dc.titleClique graphs of chordal and path graphspt_BR
dc.typeRelatóriopt_BR
dc.description.resumoNós caracterizamos os grafos clique de grafos cordiais e de caminhos. É apresentada ainda uma classe de grafos chamada árvores expandidas. Elas formam uma sub-classe dos grafos disk-Helly. Mostra-se que o grafo clique de todo grafo cordal (portanto dos de caminho) é uma árvore expandida. Mais ainda, que toda árvore expandida é o grafo clique de algum grafo de caminho (portanto cordal). Diferentes caracterizações de árvores expandidas são descritas, conduzindo a um algoritmo de tempo polinomial para o reconhecimento de grafos nesta classe.pt_BR
dc.publisher.countryBrasilpt_BR
dc.publisher.departmentInstituto Tércio Pacitti de Aplicações e Pesquisas Computacionaispt_BR
dc.subject.cnpqCNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAOpt_BR
dc.citation.issue2391pt_BR
dc.embargo.termsabertopt_BR
Appears in Collections:Relatórios Técnicos e de Pesquisa

Files in This Item:
File Description SizeFormat 
23-91.pdf908,8 kBAdobe PDFView/Open


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