Use este identificador para citar ou linkar para este item:
http://hdl.handle.net/1843/ESBF-BA8NJD
Tipo: | Dissertação de Mestrado |
Título: | Exact algorithms and computational complexity for the strong geodetic set problem |
Autor(es): | João Henrique Gonçalves de Sousa |
Primeiro Orientador: | Vinicius Fernandes dos Santos |
Primeiro Coorientador: | Sebastián Alberto Urrutia |
Primeiro membro da banca : | Sebastián Alberto Urrutia |
Segundo membro da banca: | Gabriel de Morais Coutinho |
Terceiro membro da banca: | Mitre Costa Dourado |
Quarto membro da banca: | Carlos Vinicius Gomes Costa Lima |
Resumo: | Estudamos problema do conjunto geodético forte (PCGF), um problema NP-completo de convexidade em grafos cujo objetivo é achar um conjunto geodético forte mínimo. Um conjunto geodético forte é um conjunto de vértices S no qual é possível atribuir um único caminho mínimo para cada par de vértices em S de forma que todos os vértices do grafo pertençam a pelo menos um de tais caminhos mínimos. Obtivemos resultados referentes à complexidade de tempo. Nossa abordagem foi baseada na análise do problema para diferentes classes de grafos, possibilitando a construção de uma hierarquia que especifica a complexidade do problema para grafos bipartidos, grafos co-bipartidos, grafos cordais, grafos blocos, grafos threshold, grafos cactos e árvores. Além disso, concluímos que o PCGF é um problema tratável por parâmetro fixo quando os parâmetros são o diâmetro do grafo e o parâmetro natural em conjunto. Também foi provado que o PCGF parametrizado pelo diâmetro não está em XP, fortalecendo o resultado anterior. Definimos o problema do reconhecimento de conjuntos geodéticos fortes (PRCGF), que consiste em decidir se um dado conjunto de vértices S é um conjunto geodético forte. Obtivemos uma prova da NP-Completude do PRCGF utilizando-se de uma redução a partir de uma variante do problema da satisfabilidade. Finalmente, valendo-se da forte relação entre os dois problemas citados, determinamos a complexidade computacional do PRCGF para grafos bipartidos, grafos blocos, grafos com diâmetro 2, grafos split, grafos cactos e árvores. |
Abstract: | We studied the strong geodetic set problem (SGSP), an NP-Complete convexity problem in graphs that asks for a minimum strong geodetic set. A strong geodetic set is a vertex set in which it is possible cover all vertices of the graph by assigning a shortest path for each vertex pair at the set. We achieved results concerning the computation complexity of the problem. Our approach was based mainly on analyzing the problem for different graph classes, then it was possible to construct a comprehensive graph class hierarchy specifying the complexity of the problem for bipartite graphs, co-bipartite graphs, chordal graphs, block graphs, threshold graphs, cactus graphs and trees. In addition, we stated that the SGSP is fixed parameter tractable when the parameters are the graph's diameter and the natural parameter together. Besides that, we proved that the SGSP parameterized by the diameter is not in XP, strengthening the previous result. Moreover, we defined the strong geodetic set recognition problem (SGSRP), which can be seen as a subproblem of the SGSP. We obtained a proof of the NP-Completeness of the problem, increasing the understanding of the SGSP and also gathering knowledge about a new convexity problem with interesting applications. Finally, given the strong relation between the two cited problems, we could also derive the complexity status of the SGSRP for bipartite graphs, block graphs, graphs with diameter 2, split graphs, cacti graphs and trees. |
Assunto: | Algoritmos exatos Teoria dos grafos Caminhos mínimos Computação Conjunto geodético forte Problemas NP-completo |
Idioma: | Inglês |
Editor: | Universidade Federal de Minas Gerais |
Sigla da Instituição: | UFMG |
Tipo de Acesso: | Acesso Aberto |
URI: | http://hdl.handle.net/1843/ESBF-BA8NJD |
Data do documento: | 18-Dez-2018 |
Aparece nas coleções: | Dissertações de Mestrado |
Arquivos associados a este item:
Arquivo | Descrição | Tamanho | Formato | |
---|---|---|---|---|
joaohenriquegon_alvesdesousa.pdf | 1.04 MB | Adobe PDF | Visualizar/Abrir |
Os itens no repositório estão protegidos por copyright, com todos os direitos reservados, salvo quando é indicado o contrário.