Algoritmos e limites para os números envoltório e de Carathéodory na convexidade P3

Página do item simplificado
dc.contributor.advisor-co1Silva, Hebert Coelho da
dc.contributor.advisor-co1Latteshttp://lattes.cnpq.br/4898337852702758eng
dc.contributor.advisor1Coelho, Erika Morais Martins
dc.contributor.advisor1Latteshttp://lattes.cnpq.br/9389487015938509eng
dc.contributor.referee1Coelho, Erika Morais Martins
dc.contributor.referee2Silva, Hebert Coelho da
dc.contributor.referee3Santana, Márcia Rodrigues Cappelle
dc.contributor.referee4Souza, Uéverton dos Santos
dc.creatorSilva, Braully Rocha da
dc.creator.Latteshttp://lattes.cnpq.br/6423154319465728eng
dc.date.accessioned2018-10-30T11:20:36Z
dc.date.issued2018-09-24
dc.description.abstractIn this work we present results and implementantions for hull and Carathéodory numbers in P3 convexity. We obtain results for graphs of diameter 2 having cut-vertex for both problems. Finally, entering more complex cases, we were able to determine a logarithmic limit, means of algorithm, for the hull number in case of graph diameter 2 and 2-connected. Exploring more restrictive cases, we determined a constant limit for some subclasses of graphs of diameter 2. We made also implementations and algorithms for these parameters. Implementations algorithms heuristic, parallel, and brute force. Finally, although not directly related, we developed an algorithm for Moore's graphs generation, which may be one of the ways to find Moore missinge graph, if it exists, a question that remains unknown for 55 years. And finally, we conclude with some conjectures interesting, for limits to the hull and Carathéodory numbers, in other classes of graphs, that were not explored in this work, but was identified by the implementations, and can be better explored in future works.eng
dc.description.provenanceSubmitted by Luciana Ferreira (lucgeral@gmail.com) on 2018-10-30T11:09:54Z No. of bitstreams: 2 Dissertação - Braully Rocha da Silva - 2018.pdf: 1396149 bytes, checksum: 9a9145cb07e037a784d2d15d43cbd1ff (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5)eng
dc.description.provenanceApproved for entry into archive by Luciana Ferreira (lucgeral@gmail.com) on 2018-10-30T11:20:36Z (GMT) No. of bitstreams: 2 Dissertação - Braully Rocha da Silva - 2018.pdf: 1396149 bytes, checksum: 9a9145cb07e037a784d2d15d43cbd1ff (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5)eng
dc.description.provenanceMade available in DSpace on 2018-10-30T11:20:36Z (GMT). No. of bitstreams: 2 Dissertação - Braully Rocha da Silva - 2018.pdf: 1396149 bytes, checksum: 9a9145cb07e037a784d2d15d43cbd1ff (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) Previous issue date: 2018-09-24eng
dc.description.resumoNesta dissertação, tratamos de limites para o número envoltório e o número de Carathéodory na Convexidade P3. Aferimos resultados para grafos de diâmetro 2 com vértice de corte para ambos os problemas. Adentrando em casos mais complexos, conseguimos determinar um limite logarítmico, por meio de algoritmo pseudo-polimonial, para o número envoltório de grafos de diâmetro 2 biconexos. Explorando um pouco mais restritivamente, conseguimos determinar um limite constante para algumas subclasses de grafos de diâmetro 2, os grafos maximais sem triângulo. Não atendo somente aos resultados teóricos, realizamos também implementações e algoritmos para esses parâmetros. As implementações perfazem algoritmos heurísticos, paralelos e força bruta. Por fim, embora não diretamente relacionado, desenvolvemos uma algoritmo para geração de grafos de Moore, que pode ser um dos caminhos para encontrar o ultimo grafo de Moore, caso ele exista. Questão que remanesce desconhecido e procurada por 55 anos.eng
dc.description.sponsorshipOutroeng
dc.formatapplication/pdf*
dc.identifier.citationSILVA, B. R. Algoritmos e limites para os números envoltório e de Carathéodory na convexidade P3. 2018. 93 f. Dissertação (Mestrado em Ciência da Computação) - Universidade Federal de Goiás, Goiânia, 2018.eng
dc.identifier.urihttp://repositorio.bc.ufg.br/tede/handle/tede/9008
dc.languageporeng
dc.publisherUniversidade Federal de Goiáseng
dc.publisher.countryBrasileng
dc.publisher.departmentInstituto de Informática - INF (RG)eng
dc.publisher.initialsUFGeng
dc.publisher.programPrograma de Pós-graduação em Ciência da Computação (INF)eng
dc.rightsAcesso Aberto
dc.rights.urihttp://creativecommons.org/licenses/by-nc-nd/4.0/
dc.subjectConvexidade P3por
dc.subjectNúmero envoltóriopor
dc.subjectNúmero Carathéodorypor
dc.subjectHull numbereng
dc.subjectCarathéodory numbereng
dc.subjectP3 convexityeng
dc.subject.cnpqCIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAOeng
dc.titleAlgoritmos e limites para os números envoltório e de Carathéodory na convexidade P3eng
dc.title.alternativeAlgorithms and limits for hull and Carathéodory numbers in P3 convexityeng
dc.typeDissertaçãoeng

Arquivos

Pacote Original
Agora exibindo 1 - 1 de 1
Nenhuma Miniatura disponível
Nome:
Dissertação - Braully Rocha da Silva - 2018.pdf
Tamanho:
1.33 MB
Formato:
Adobe Portable Document Format
Descrição:
Baixar
Licença do Pacote
Agora exibindo 1 - 1 de 1
Nenhuma Miniatura disponível
Nome:
license.txt
Tamanho:
2.11 KB
Formato:
Item-specific license agreed upon to submission
Descrição:
Baixar

Coleções

Mestrado em Ciência da Computação (INF)