Please use this identifier to cite or link to this item: http://www.repositorio.ufc.br/handle/riufc/39396
Title in Portuguese: Resultados no tempo máximo e no número de envoltória nas convexidades p3 e geodésica
Author: Marcilon, Thiago Braga
Advisor(s): Sampaio, Rudini Menezes
Keywords: Convexidade em grafos
Número de envoltória
Tempo máximo de infecção
Complexidade clássica
Complexidade parametrizada
Issue Date: 2017
Citation: MARCILON, Thiago Braga. Resultados no tempo máximo e no número de envoltória nas convexidades p3 e geodésica. 2017. 188 f. Tese (Doutorado em Ciência da Computação) - Universidade Federal do Ceará, Fortaleza, 2017.
Abstract in Portuguese: Convexidade em grafos é um conceito inspirado na convexidade da geometria euclidiana e vem sendo bastante explorado nas últimas décadas. Muitas aplicações reais como a difusão de uma infecção ou de informação em uma rede social podem ser modeladas usando alguma convexidade em grafos baseada em caminhos do grafo. Nesta tese, nós abordamos dois problemas computacionais relacionados à convexidade em grafos: Número de Envoltória e Tempo Máximo de Infecção. Fixada uma convexidade C, o problema Número de Envoltória consiste em, dados um grafo G e inteiro k, determinar se o número de envoltória de G na convexidade C é no máximo k. O problema Tempo Máximo de Infecção consiste em, dados um grafo G e inteiro k, determinar se o tempo máximo de infecção de G na convexidade C é no mínimo k. Apresentamos algoritmos polinomiais para o problema Tempo Máximo de Infecção na convexidade P3 em algumas classes de grafos e para k fixo. Apresentamos também algoritmos tratáveis por parâmetro fixo na combinação dos parâmetros grau máximo do grafo e k e na combinação dos parâmetros largura em árvore do grafo e k. Também apresentamos resultados de NP-completude para o problema Tempo Máximo de Infecção na convexidade P3 em algumas classes de grafos e para algumas restrições da entrada k. Apresentamos ainda a sua W[1]-dificuldade para o parâmetro largura em árvore. Finalmente, mostramos que o problema Número de Envoltória na convexidade P3 é W[1]-difícil no parâmetro k em grafos livres de K3 com grau máximo seis. Mostramos também que o problema Número de Envoltória na convexidade geodésica é W[1]-difícil no parâmetro k em grafos com diâmetro dois e na combinação dos parâmetros largura em árvore e k. Apresentamos ainda um algoritmo XP no parâmetro largura em árvore que calcula o número de envoltória de um grafo na convexidade geodésica.
Abstract: Graph convexity is a concept inspired by the convexity notions in the euclidian geometry and has been receiving a lot of attention in the last few decades. Several real world applications like spread of an infection or information in a social network can be modeled using some graph convexity based on paths in the graph. In this thesis, we consider two computational problems relating to graph convexity: Hull Number and Maximum Infection Time. Fixed a convexity C, the Hull Number problem consists in, given a graph G and an integer k, determine whether the hull number of G in the convexity C is at most k. The Maximum Infection Time problem consists in, given a graph G and an integer k, determine whether the hull number of G in the convexity C is at least k. We present some polynomial algorithms for the Maximum Infection Time problem in the P3 convexity for some graph classes and when we fix the input k. We also present fixed parameter tractable algorithms when we combine the parameters maximum degree of the graph and the input k and when we combine the parameters treewidth of the graph and the input k. Additionally, we present NP-completeness results for the Maximum Infection Time problem in the P3 convexity for some graph classes and when we restrict the input k. We also prove that the problem is W[1]-hard when parameterized by the treewidth of the graph. Finally, we show that the Hull Number problem in the P3 convexity is W[1]-hard when parameterized by k even in K3-free graphs with maximum degree six. We also show that the Hull Number problem in the geodesic convexity is W[1]-hard when parameterized by k even in graphs with diameter two and when we combine the parameters treewidth of the graph and k. Furthermore, we present a XP algorithm parameterized by the treewidth of the graph that computes the hull number of a graph in the geodesic convexity.
URI: http://www.repositorio.ufc.br/handle/riufc/39396
Appears in Collections:DCOMP - Teses defendidas na UFC

Files in This Item:
File Description SizeFormat 
2017_tese_tbmarcilon.pdf1,92 MBAdobe PDFView/Open


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