ARAÚJO, Rafael Teixeira de. Convexidades de caminhos e convexidades geométricas. 2014. 52 f. Dissertação (Mestrado em ciência da computação)- Universidade Federal do Ceará, Fortaleza-CE, 2014. / Submitted by Elineudson Ribeiro (elineudsonr@gmail.com) on 2016-07-12T16:01:23Z No. of bitstreams: 1 2014_dis_rtaraujo.pdf: 997190 bytes, checksum: 1adad553da251fa0f87bb80fbe452db4 (MD5) / Approved for entry into archive by Rocilda Sales (rocilda@ufc.br) on 2016-07-21T16:02:42Z (GMT) No. of bitstreams: 1 2014_dis_rtaraujo.pdf: 997190 bytes, checksum: 1adad553da251fa0f87bb80fbe452db4 (MD5) / Made available in DSpace on 2016-07-21T16:02:42Z (GMT). No. of bitstreams: 1 2014_dis_rtaraujo.pdf: 997190 bytes, checksum: 1adad553da251fa0f87bb80fbe452db4 (MD5) Previous issue date: 2014 / In this dissertation we present complexity results related to the hull number and the convexity number for P3 convexity. We show that the hull number and the convexity number are NP-hard even for bipartite graphs. Inspired by our research in convexity based on paths, we introduce a new convexity, where we defined as convexity of induced paths of order three or P∗ 3 . We show a relation between the geodetic convexity and the P∗ 3 convexity when the graph is a join of a Km with a non-complete graph. We did research in geometric convexity and from that we characterized graph classes under some convexities such as the star florest in P3 convexity, chordal cographs in P∗ 3 convexity, and the florests in TP convexity. We also demonstrated convexities that are geometric only in specific graph classes such as cographs in P4+-free convexity, F free graphs in F-free convexity and others. Finally, we demonstrated some results of geodesic convexity and P∗ 3 in graphs with few P4’s. / Nessa dissertação apresentamos resultados de complexidade relativos ao número de hull e o número de convexidade na convexidade P3. Mostramos que o número de hull e o número de convexidade é NP-difícil mesmo em grafos bipartidos. Motivados por nossa pesquisa em convexidade baseada em caminhos introduzimos uma nova convexidade a qual definimos como convexidade dos caminhos induzidos de ordem três ou P∗ 3 . Mostramos uma relação da convexidade geodésica com a convexidade P∗ 3 no caso onde o grafo ´e uma jun¸c˜ao de um Km com um grafo n˜ao completo. Estudamos também convexidade geométrica e caracterizamos algumas classes de grafos em determinadas convexidade como as florestas de estrela na convexidade P3, cografos cordais na convexidade P∗ 3 , e as florestas na convexidade TP. Mostramos também convexidades que são geométricas somente em uma determinada classe de grafos como os cografos na convexidade P4+-free, os grafos livres de F na convexidade F-free entre outras. Por fim demonstramos alguns resultados de convexidade geodésica e P∗ 3 na em grafos com poucos P4’s.

COSTA, Eurinardo Rodrigues. Convexidade Monofônica em Classes de Grafos. 2016. 54 f. Dissertação (mestrado em ciência da computação)- Universidade Federal do Ceará, Fortaleza-CE, 2016. / Submitted by Elineudson Ribeiro (elineudsonr@gmail.com) on 2016-03-22T19:02:45Z No. of bitstreams: 1 2016_dis_ercosta.pdf: 1611008 bytes, checksum: 4733a7aa273b8370fc06126fca5dc15a (MD5) / Approved for entry into archive by Rocilda Sales (rocilda@ufc.br) on 2016-05-12T11:58:17Z (GMT) No. of bitstreams: 1 2016_dis_ercosta.pdf: 1611008 bytes, checksum: 4733a7aa273b8370fc06126fca5dc15a (MD5) / Made available in DSpace on 2016-05-12T11:58:17Z (GMT). No. of bitstreams: 1 2016_dis_ercosta.pdf: 1611008 bytes, checksum: 4733a7aa273b8370fc06126fca5dc15a (MD5) Previous issue date: 2016 / In this work, we study some parameters of monophonic convexity in some classes of graphs and we present our results about this subject. We prove that decide if the $m$-interval number is at most 2 and decide if the $m$-percolation time is at most 1 are NP-complete problems even on bipartite graphs. We also prove that the $m$-convexity number is as hard to approximate as the maximum clique problem, which is, $O(n^{1-varepsilon})$-unapproachable in polynomial-time, unless P=NP, for each $varepsilon>0$. Finally, we obtain polynomial time algorithms to compute the $m$-convexity number on hereditary graph classes such that the computation of the clique number is polynomial-time solvable (e.g. perfect graphs and planar graphs). / Neste trabalho, estudamos alguns parâmetros para a convexidade monofônica em algumas classes de grafos e apresentamos nossos resultados acerca do assunto. Provamos que decidir se o número de $m$-intervalo é no máximo 2 e decidir se o tempo de $m$-percolação é no máximo 1 são problemas NP-completos mesmo em grafos bipartidos. Também provamos que o número de $m$-convexidade é tão difícil de aproximar quanto o problema da Clique Máxima, que é, $O(n^{1-varepsilon})$-inaproximável em tempo polinomial, a menos que P=NP, para cada $varepsilon>0$. Finalmente, apresentamos um algoritmo de tempo polinomial para determinar o número de $m$-convexidade em classes hereditárias de grafos onde a computação do tamanho da clique máxima é em tempo polinomial (como grafos perfeitos e grafos planares).