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

Saved in:

Bibliografiske detaljer
Hovedforfatter:	Silva, Braully Rocha da
Publication Date:	2018
Format:	Master thesis
Sprog:	por
Source:	Repositório Institucional da UFG
Download full:	http://repositorio.bc.ufg.br/tede/handle/tede/9008
Summary:	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.

Lignende værker: Algoritmos e limites para os números envoltório e de Carathéodory na convexidade P3