Please use this identifier to cite or link to this item: http://hdl.handle.net/11422/12956
Full metadata record
DC FieldValueLanguage
dc.contributor.advisorSzwarcfiter, Jayme Luiz-
dc.contributor.authorPinto, José Wilson Coura.-
dc.date.accessioned2020-08-21T12:42:35Z-
dc.date.available2023-12-21T03:02:14Z-
dc.date.issued2018-09-
dc.identifier.urihttp://hdl.handle.net/11422/12956-
dc.description.abstractIntersection graphs are a topic that has attracted great interest from researchers in the area of graph theory since the 1960s. In this thesis we study the intersection graphs of subtrees of a tree. More precisely we will present results on the class of graphs ORTH[h, s, t]. The graphs that belong to this class are those that admit a representation by intersection of subtrees of a host tree, in which the maximum degree of the host tree is h, the maximum degree of any subtree is s, all leaves of the subtree are also leaves of the host tree and two vertices are adjacent in the graph if and only if their corresponding subtrees have at least t nodes in common and at least one of these nodes is a leaf. Results of representability, non-representability and complexity for classes ORTH[h, s, t] with the different values of the parameters h, s or t are present in this work.pt_BR
dc.languageporpt_BR
dc.publisherUniversidade Federal do Rio de Janeiropt_BR
dc.rightsAcesso Abertopt_BR
dc.subjectGrafos de Interseçãopt_BR
dc.subjectGrafos linhapt_BR
dc.titleGrafos ORTH[h, s, t] /pt_BR
dc.typeTesept_BR
dc.contributor.advisorLatteshttp://lattes.cnpq.br/2002515486942024pt_BR
dc.contributor.authorLatteshttp://lattes.cnpq.br/0431627623206228pt_BR
dc.contributor.referee1Bornstein, Claudson Ferreira-
dc.contributor.referee2Cerioli, Marcia Rosana-
dc.contributor.referee3Cerioli, Marcia Rosana-
dc.contributor.referee4Bravo, Raquel de Souza Francisco-
dc.description.resumoGrafos de interseção é um assunto que desperta grande interesse de pesquisadores da área de teoria dos grafos desde a década de 60. Nesta tese estudamos os grafos de interseção de subárvores de uma árvore. Mais precisamente vamos apresentar resultados sobre a classe de grafos ORTH[h, s, t]. Os grafos que pertencem a esta classe são aqueles que admitem uma representação por interseção de subárvores de uma árvore hospedeira, na qual o grau máximo da árvore hospedeira é h, o grau máximo de qualquer subárvore é s, todas as folhas das subárvores também são folhas da árvore hospedeira e dois vértices são adjacentes no grafo se e somente se suas subárvores correspondentes possuem no mínimo t nós em comum e ao menos um destes nós é uma folha. Resultados de representabilidade, não-representabilidade e complexidade para classes ORTH[h, s, t] com a variação do valores dos parâmetros h, s ou t estão presentes neste trabalho.pt_BR
dc.publisher.countryBrasilpt_BR
dc.publisher.departmentInstituto Alberto Luiz Coimbra de Pós-Graduação e Pesquisa de Engenhariapt_BR
dc.publisher.programPrograma de Pós-Graduação em Engenharia de Sistemas e Computaçãopt_BR
dc.publisher.initialsUFRJpt_BR
dc.subject.cnpqCNPQ::ENGENHARIASpt_BR
dc.embargo.termsabertopt_BR
Appears in Collections:Engenharia de Sistemas e Computação

Files in This Item:
File Description SizeFormat 
JoseWilsonCouraPinto-min.pdf954.15 kBAdobe PDFView/Open


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