Pantheon Repositorio Institucional
Recopila, preserva y difundi la producción académica digital en todas las áreas del conocimiento.
Comprende los activos del repositorio, además de tesis y disertaciones en la UFRJ, artículos científicos, libros electrónicos, capítulos de libros y trabajos presentados en eventos para los profesores, investigadores, personal administrativo y estudiantes de maestría y doctorado.
Por favor, use este identificador para citar o enlazar este ítem:
http://hdl.handle.net/11422/12956| Especie: | Tese |
| Título : | Grafos ORTH[h, s, t] / |
| Autor(es)/Inventor(es): | Pinto, José Wilson Coura. |
| Tutor: | Szwarcfiter, Jayme Luiz |
| Resumen: | Grafos 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. |
| Resumen: | Intersection 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. |
| Materia: | Grafos de Interseção Grafos linha |
| Materia CNPq: | CNPQ::ENGENHARIAS |
| Programa: | Programa de Pós-Graduação em Engenharia de Sistemas e Computação |
| Unidade de producción: | Instituto Alberto Luiz Coimbra de Pós-Graduação e Pesquisa de Engenharia |
| Editor: | Universidade Federal do Rio de Janeiro |
| Fecha de publicación: | sep-2018 |
| País de edición : | Brasil |
| Idioma de publicación: | por |
| Tipo de acceso : | Acesso Aberto |
| Aparece en las colecciones: | Engenharia de Sistemas e Computação |
Ficheros en este ítem:
| Fichero | Descripción | Tamaño | Formato | |
|---|---|---|---|---|
| JoseWilsonCouraPinto-min.pdf | 954.15 kB | Adobe PDF | Visualizar/Abrir |
Los ítems de DSpace están protegidos por copyright, con todos los derechos reservados, a menos que se indique lo contrario.