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

URI Permanente para esta coleção

http://200.137.215.59/tede/handle/tde/225

Navegar

Navegando Mestrado em Ciência da Computação (INF) por Por Orientador "Coelho, Erika Morais Martins"

Agora exibindo 1 - 3 de 3
  • Nenhuma Miniatura disponível
    Item
    O número de Carathéodory na convexidade geodésica de grafos
    (Universidade Federal de Goiás, 2016-12-01) Lira, Eduardo Silva; Castonguay, Diane; http://lattes.cnpq.br/4005898623592261; Coelho, Erika Morais Martins; http://lattes.cnpq.br/9389487015938509; Coelho, Erika Morais Martins; Castonguay, Diane; Santana, Márcia Rodrigues Cappelle; Szwarcfiter, Jayme Luiz
    From Carathéodory’s theorem arises the definition of the Carathéodory number for graphs. This number is well-known for monophonic and triangle-path convexities. It is limited for some classes of graphs on P3 and geodesic convexities but is known to be unlimited only on P3-convexity. Driven by open questions in geodesic convexity, in this work we study the Carathéodory number in this convexity. For general graphs and cartesian product, we prove that the Carathéodory number is unlimited. We characterize the Carathéodory number for trees, cographs, for the complementary prisms of cographs and simple graphs Kn, Pn and Cn, for the complement and the complementary prism of the graph KnKn and for the cartesian products PnxPm, KnxKm and PnxKm.
  • Nenhuma Miniatura disponível
    Item
    O número envoltório P3 e o número envoltório geodético em produtos de grafos
    (Universidade Federal de Goiás, 2016-11-30) Nascimento, Julliano Rosa; Szwarcfiter, Jayme Luiz; http://lattes.cnpq.br/2002515486942024; Coelho, Erika Morais Martins; http://lattes.cnpq.br/9389487015938509; Coelho, Erika Morais Martins; http://lattes.cnpq.br/9389487015938509; Szwarcfiter, Jayme Luiz; http://lattes.cnpq.br/2002515486942024; Centeno, Carmen Cecilia; Dias, Elisângela Silva
    In this work, we consider the parameter hull number in two graph convexities, the P3- convexity and the geodetic convexity. In the P3-convexity, we present results on the P3- hull number on the Cartesian product, strong product and lexicographic product of graphs. In special, regarding to the Cartesian product, we proved a complexity result, in which we show, given a graph G resulting of a Cartesian product of two graphs and a positive integer k, is NP-complete to decide whether the P3-hull number of G is less than or equal k. We also consider the P3-hull number on complementary prisms GG of connected graphs G and G, in which we show a tighter upper bound than that found in the literature. In the geodetic convexity, we show results of the hull number on complementary prisms GG when G is a tree, when G is a disconnected graph and when G is a cograph. Finally, we also show that in the geodetic convexity, the hull number on the complementary prism GG is unlimited on connected graphs G and G, unlike what happens in the P3-convexity
  • Nenhuma Miniatura disponível
    Item
    Algoritmos e limites para os números envoltório e de Carathéodory na convexidade P3
    (Universidade Federal de Goiás, 2018-09-24) Silva, Braully Rocha da; Silva, Hebert Coelho da; http://lattes.cnpq.br/4898337852702758; Coelho, Erika Morais Martins; http://lattes.cnpq.br/9389487015938509; Coelho, Erika Morais Martins; Silva, Hebert Coelho da; Santana, Márcia Rodrigues Cappelle; Souza, Uéverton dos Santos
    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.