Algoritmos e limites para os números envoltório e de Carathéodory na convexidade P3
Nenhuma Miniatura disponível
Data
2018-09-24
Autores
Título da Revista
ISSN da Revista
Título de Volume
Editor
Universidade Federal de Goiás
Resumo
In 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.
Descrição
Palavras-chave
Citação
SILVA, 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.