1. Repositório Institucional da UFMG
  2. Trabalhos Acadêmicos
  3. Dissertações e Teses
  4. Pós-Graduação em Ciência da Computação
  5. Dissertações de Mestrado
Please use this identifier to cite or link to this item: http://hdl.handle.net/1843/ESBF-BA8NJD
Full metadata record
DC FieldValueLanguage
dc.contributor.advisor1Vinicius Fernandes dos Santospt_BR
dc.contributor.advisor-co1Sebastián Alberto Urrutiapt_BR
dc.contributor.referee1Sebastián Alberto Urrutiapt_BR
dc.contributor.referee2Gabriel de Morais Coutinhopt_BR
dc.contributor.referee3Mitre Costa Douradopt_BR
dc.contributor.referee4Carlos Vinicius Gomes Costa Limapt_BR
dc.creatorJoão Henrique Gonçalves de Sousapt_BR
dc.date.accessioned2019-08-11T21:39:52Z-
dc.date.available2019-08-11T21:39:52Z-
dc.date.issued2018-12-18pt_BR
dc.identifier.urihttp://hdl.handle.net/1843/ESBF-BA8NJD-
dc.description.abstractWe 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.pt_BR
dc.description.resumoEstudamos 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.pt_BR
dc.languageInglêspt_BR
dc.publisherUniversidade Federal de Minas Geraispt_BR
dc.publisher.initialsUFMGpt_BR
dc.rightsAcesso Abertopt_BR
dc.subjectalgoritmos exatospt_BR
dc.subjectcomplexidade parametrizadapt_BR
dc.subjectNP-completudept_BR
dc.subjectclasses de grafospt_BR
dc.subjectcaminhos mínimospt_BR
dc.subjectConjunto geodético fortept_BR
dc.subject.otherAlgoritmos exatospt_BR
dc.subject.otherTeoria dos grafospt_BR
dc.subject.otherCaminhos mínimospt_BR
dc.subject.otherComputaçãopt_BR
dc.subject.otherConjunto geodético fortept_BR
dc.subject.otherProblemas NP-completopt_BR
dc.titleExact algorithms and computational complexity for the strong geodetic set problempt_BR
dc.typeDissertação de Mestradopt_BR
Appears in Collections:Dissertações de Mestrado

Files in This Item:
File Description SizeFormat 
joaohenriquegon_alvesdesousa.pdf1.04 MBAdobe PDFView/Open
Show simple item record


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