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.

FundaÃÃo Cearense de Apoio ao Desenvolvimento Cientifico e TecnolÃgico / 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. / 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.

Made available in DSpace on 2015-09-17T15:24:10Z (GMT). No. of bitstreams: 0 Previous issue date: 2013-12-20. Added 1 bitstream(s) on 2015-09-17T15:48:16Z : No. of bitstreams: 1 000846652.pdf: 1343997 bytes, checksum: 1000b508cfe00cf80877428e4f647e0e (MD5) / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES) / Neste trabalho consideramos dois problemas variacionais com restrições Lagrangeanas do tipo g(t, x(t), x_ (t)) = 0. Apresentamos vários resultados sobre condições su cientes de otimalidade Kuhn-Tucker supondo invexidade generalizada das funções envolvidas. Introduzimos duas de nições para os problemas variacionais estudados, a primeira chamada de L-KT-pseudo-invexidade, que envolve os multiplicadores Lagrangeanos, e a segunda chamada de KT-pseudo-invexidade, que não envolve os multiplicadores Lagrangeanos. Apresentamos uma caracterização dos problemas variacionais L-KT-pseudo-invexos como sendo aqueles problemas onde todos seus pontos Kuhn-Tucker são soluções ótimas. Finalmente mostramos que, sob algumas condições, L-KT-pseudo-invexidade é equivalente a KT-pseudo-invexidade / In this work we consider two variational problems with Lagrangian constraints of type g(t, x(t), x_ (t)) = 0. We present several results on su cient conditions for Kuhn-Tucker optimality assuming generalized invexity of the functions involved. We introduce two de nitions for the variational problems, the rst called L-KT-pseudo-invexity, which involves the Lagrangian multipliers and the second called KT-pseudo-invexity, which does not involve the Lagrangian multipliers. We present a characterization of L-KTpseudo- invex variational problems as those problems where all Kuhn-Tucker points are optimal solutions. Finally we show that, under some conditions, L-KT-pseudo-invexity is equivalent to KT-pseudo-invexity

Dissertação (mestrado)—Universidade de Brasília, Departamento de Economia, 2006. / Submitted by Alexandre Marinho Pimenta (alexmpsin@hotmail.com) on 2009-10-03T15:53:14Z No. of bitstreams: 1 2006_Mauricio da Silva Venancio Pires.pdf: 1521638 bytes, checksum: f842fa409e632dbddeb3d6b810512d03 (MD5) / Approved for entry into archive by Gomes Neide(nagomes2005@gmail.com) on 2010-06-10T18:53:05Z (GMT) No. of bitstreams: 1 2006_Mauricio da Silva Venancio Pires.pdf: 1521638 bytes, checksum: f842fa409e632dbddeb3d6b810512d03 (MD5) / Made available in DSpace on 2010-06-10T18:53:05Z (GMT). No. of bitstreams: 1 2006_Mauricio da Silva Venancio Pires.pdf: 1521638 bytes, checksum: f842fa409e632dbddeb3d6b810512d03 (MD5) Previous issue date: 2006 / A pesquisa objetiva testar empiricamente, se as estratégias de imunização pela duration e pela convexidade – a “Trava Borboleta” – utilizadas no mercado internacional como instrumentos de hegde para a variação de taxas de juros em títulos, são eficientes quando aplicadas aos títulos emitidos em dólares pelo governo brasileiro no mercado global – os Brazilian Global Bonds. __________________________________________________________________________________________ ABSTRACT / The research aims to empirically test whether the strategies of immunization by duration and by convexity - The Butterfly Trade – used in the international market as hedge instruments for bonds interest rate variation are efficient when applied to bonds issued in dollars by Brazilian government in the global market - the Brazilian Global Bonds.

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).

A presente dissertação aborda pesquisas recentes sobre dois tópicos distintos da Matemática. Não é a primeira vez que as conexões entre geometria e álgebra são frutíferas, mas é somente agora que as idéias geométricas estão sendo aplicadas efetivamente na fatoração de polinômios, um tema puramente algébrico. Mais especificamente, estudamos a decomposição de politopos e suas aplicações na fatoração de polinômios. Começamos apresentando construções de politopos integralmente indecomponíveis que levam a critérios de irredutibilidade de polinômios. Estudamos detalhadamente algoritmos para a decomposição de politopos, sempre ilustrados com exemplos e comentários sobre suas aplicações. Terminamos apresentando um algoritmo desenvolvido por Fatima Salem, Shuhong Gao e Alan Lauder, que fatora polinômios bivariados a partir da decomposição do seu politopo de Newton associado. Esse algoritmo é um marco nessa área já que traduz, pela primeira vez, de forma eficiente, idéias geométricas para a fatoração polinomial, usando uma técnica similar ao levantamento de Hensel. / The present work deals with recent research about two distinct mathematical topics. It is not the first time that connections between geometry and algebra are fruitful, but it is only now that geometric ideas are being applied effectively in polynomial factorization, a purely algebraic theme. More specifically we study the decomposition of polytopes and their applications on polynomial factorization. We begin studying construction of indecomposable polytopes which give many irreducibility criteria polynomial. We study thoroughly algorithms for decomposition of polytopes, always illustrated with examples and comments about their applications. We finish presenting an algorithm developed by Fatima Salem, Shuhong Gao and Alan Lauder for factoring bivariate polynomials from the decomposition of the Newton polytope associated. This algorithm is a mark land in the field since it translate, for the first time, effectivelly, geometric ideas for polynomial factorization using a technic similar to Hensel lifting.

ARAÚJO, Júlio César Silva. Coloração em convexidade em grafos. 2012. 207 f. Tese (Mestrado em ciência da computação)- Universidade Federal do Ceará, Fortaleza-CE, 2012. / Submitted by Elineudson Ribeiro (elineudsonr@gmail.com) on 2016-08-04T12:28:10Z No. of bitstreams: 1 2012_tese_jcsaraujo.pdf: 2148108 bytes, checksum: 966c00be231160cb1e161402770627d6 (MD5) / Approved for entry into archive by Rocilda Sales (rocilda@ufc.br) on 2016-08-05T15:46:03Z (GMT) No. of bitstreams: 1 2012_tese_jcsaraujo.pdf: 2148108 bytes, checksum: 966c00be231160cb1e161402770627d6 (MD5) / Made available in DSpace on 2016-08-05T15:46:03Z (GMT). No. of bitstreams: 1 2012_tese_jcsaraujo.pdf: 2148108 bytes, checksum: 966c00be231160cb1e161402770627d6 (MD5) Previous issue date: 2012 / In this thesis, we study several problems of Graph Theory concerning Graph Coloring and Graph Convexity. Most of the results contained here are related to the computational complexity of these problems for particular graph classes. In the first and main part of this thesis, we deal with Graph Coloring which is one of the most studied areas of Graph Theory. We first consider three graph coloring problems called Greedy Coloring, Weighted Coloring and Weighted Improper Coloring. Then, we deal with a decision problem, called Good Edge-Labeling, whose de finition was motivated by the Wavelength Assignment problem in optical networks. The second part of this thesis is devoted to a graph optimization parameter called (geodetic) hull number. The de finition of this parameter is motivated by an extension to graphs of the notions of convex sets and convex hulls in the Euclidean space. Finally, we present in the appendix other works developed during this thesis, one about Eulerian and Hamiltonian directed hypergraphs and the other concerning distributed storage systems. / Nesta tese, estudamos vários problemas de teoria dos grafos relativos à coloração e convexidade em grafos. A maioria dos resultados contidos aqui são ligados à complexidade computacional destes problemas para classes de grafos particulares. Na primeira, e principal, parte desta tese, discutimos coloração de grafos que é uma das áreas mais importantes de teoria dos grafos. Primeiro, consideramos três problemas de coloração chamados coloração gulosa, coloração ponderada e coloração ponderada imprópria. Em seguida, discutimos um problema de decisão, chamado boa rotulagem de arestas, cuja de finição foi motivada pelo problema de atribuição de frequências em redes óticas. A segunda parte desta tese é dedicada a um parâmetro de otimização em grafos chamado de número de fecho (geodético). A de finição deste parâmetro é motivada pela extensão das noções de conjuntos e fecho convexos no espaço Euclidiano. Por m, apresentamos em anexo outros trabalhos desenvolvidos durante esta tese, um em hipergrafos dirigidos Eulerianos e Hamiltonianos e outro sobre sistemas de armazenamento distribuído.

SOARES, R. P. Jogos de perseguição-evasão, decomposições e convexidade em grafos. 2013. 206 f. (Doutorado em Ciência da Computação) - Centro de Ciências, Universidade Federal do Ceará, Fortaleza, 2013. / Submitted by Daniel Eduardo Alencar da Silva (dealencar.silva@gmail.com) on 2015-01-23T18:11:52Z No. of bitstreams: 1 2013_tese_rpsoares.pdf: 1865132 bytes, checksum: e9214578093ec3c62c3eee11e731fdc6 (MD5) / Approved for entry into archive by José Jairo Viana de Sousa(jairo@ufc.br) on 2015-11-25T13:04:50Z (GMT) No. of bitstreams: 1 2013_tese_rpsoares.pdf: 1865132 bytes, checksum: e9214578093ec3c62c3eee11e731fdc6 (MD5) / Made available in DSpace on 2015-11-25T13:04:50Z (GMT). No. of bitstreams: 1 2013_tese_rpsoares.pdf: 1865132 bytes, checksum: e9214578093ec3c62c3eee11e731fdc6 (MD5) Previous issue date: 2013 / Esta tese é centrada no estudo de propriedades estruturais de grafos cujas compressões permitem a concepção de algoritmos eficientes para resolver problemas de otimização. Estamos particularmente interessados em decomposições, em jogos de perseguição-evasão e em convexidade. O jogo de Processo foi definido como um modelo para a reconfiguração de roteamento em redes WDM. Muitas vezes, jogos de perseguição-evasão, em que uma equipe de agentes tem como objetivo limpar um grafo não direcionado, estão intimamente relacionados com decomposições em grafos. No caso de grafos direcionados, mostramos que o jogo de Processo é monotônico e definimos uma nova decomposição em grafos equivalente a tal jogo. A partir de então, investigamos outras decomposições em grafos. Propomos um algoritmo FPT para calcular vários parâmetros de largura em grafos. Em particular, este é o primeiro algoritmo FPT para calcular a largura em árvore especial e a largura em árvore q-ramificada de um grafo. Em seguida, estudamos um outro jogo perseguição-evasão que modela problemas de pré-obtenção. Nós introduzimos uma versão mais realista do jogo de Vigilância a versão on-line. Estudamos a diferença entre o jogo de Vigilância clássico e suas versões conectadas e on-line, fornecendo novos limites para essa diferença. Nós, então, definimos um modelo geral para o estudo de jogos perseguição-evasão, com base em técnicas de programação linear. Este método permite-nos dar os primeiros resultados de aproximação para alguns desses jogos. Finalmente, estudamos outro parâmetro relacionado com a convexidade e a propagação da infecção em redes, o “hull number”. Nós fornecemos vários resultados de complexidade computacional, dependendo das propriedades estruturais do grafo de entrada e usando decomposições em grafos. Alguns destes resultados respondem problemas em aberto na literatura.

A presente dissertação aborda pesquisas recentes sobre dois tópicos distintos da Matemática. Não é a primeira vez que as conexões entre geometria e álgebra são frutíferas, mas é somente agora que as idéias geométricas estão sendo aplicadas efetivamente na fatoração de polinômios, um tema puramente algébrico. Mais especificamente, estudamos a decomposição de politopos e suas aplicações na fatoração de polinômios. Começamos apresentando construções de politopos integralmente indecomponíveis que levam a critérios de irredutibilidade de polinômios. Estudamos detalhadamente algoritmos para a decomposição de politopos, sempre ilustrados com exemplos e comentários sobre suas aplicações. Terminamos apresentando um algoritmo desenvolvido por Fatima Salem, Shuhong Gao e Alan Lauder, que fatora polinômios bivariados a partir da decomposição do seu politopo de Newton associado. Esse algoritmo é um marco nessa área já que traduz, pela primeira vez, de forma eficiente, idéias geométricas para a fatoração polinomial, usando uma técnica similar ao levantamento de Hensel. / The present work deals with recent research about two distinct mathematical topics. It is not the first time that connections between geometry and algebra are fruitful, but it is only now that geometric ideas are being applied effectively in polynomial factorization, a purely algebraic theme. More specifically we study the decomposition of polytopes and their applications on polynomial factorization. We begin studying construction of indecomposable polytopes which give many irreducibility criteria polynomial. We study thoroughly algorithms for decomposition of polytopes, always illustrated with examples and comments about their applications. We finish presenting an algorithm developed by Fatima Salem, Shuhong Gao and Alan Lauder for factoring bivariate polynomials from the decomposition of the Newton polytope associated. This algorithm is a mark land in the field since it translate, for the first time, effectivelly, geometric ideas for polynomial factorization using a technic similar to Hensel lifting.

A presente dissertação aborda pesquisas recentes sobre dois tópicos distintos da Matemática. Não é a primeira vez que as conexões entre geometria e álgebra são frutíferas, mas é somente agora que as idéias geométricas estão sendo aplicadas efetivamente na fatoração de polinômios, um tema puramente algébrico. Mais especificamente, estudamos a decomposição de politopos e suas aplicações na fatoração de polinômios. Começamos apresentando construções de politopos integralmente indecomponíveis que levam a critérios de irredutibilidade de polinômios. Estudamos detalhadamente algoritmos para a decomposição de politopos, sempre ilustrados com exemplos e comentários sobre suas aplicações. Terminamos apresentando um algoritmo desenvolvido por Fatima Salem, Shuhong Gao e Alan Lauder, que fatora polinômios bivariados a partir da decomposição do seu politopo de Newton associado. Esse algoritmo é um marco nessa área já que traduz, pela primeira vez, de forma eficiente, idéias geométricas para a fatoração polinomial, usando uma técnica similar ao levantamento de Hensel. / The present work deals with recent research about two distinct mathematical topics. It is not the first time that connections between geometry and algebra are fruitful, but it is only now that geometric ideas are being applied effectively in polynomial factorization, a purely algebraic theme. More specifically we study the decomposition of polytopes and their applications on polynomial factorization. We begin studying construction of indecomposable polytopes which give many irreducibility criteria polynomial. We study thoroughly algorithms for decomposition of polytopes, always illustrated with examples and comments about their applications. We finish presenting an algorithm developed by Fatima Salem, Shuhong Gao and Alan Lauder for factoring bivariate polynomials from the decomposition of the Newton polytope associated. This algorithm is a mark land in the field since it translate, for the first time, effectivelly, geometric ideas for polynomial factorization using a technic similar to Hensel lifting.