ARAÚJO, Júlio César Silva. Coloração e convexidade em grafos. 2012. 207 f. Tese (Doutorado em ciência da computação)- Universidade Federal do Ceará, Fortaleza-CE, 2012. / Submitted by Elineudson Ribeiro (elineudsonr@gmail.com) on 2016-09-09T13:56:50Z No. of bitstreams: 1 2012_tese_jcsaraujo.pdf: 2148108 bytes, checksum: 966c00be231160cb1e161402770627d6 (MD5) / Approved for entry into archive by Jairo Viana (jairo@ufc.br) on 2016-09-27T23:24:47Z (GMT) No. of bitstreams: 1 2012_tese_jcsaraujo.pdf: 2148108 bytes, checksum: 966c00be231160cb1e161402770627d6 (MD5) / Made available in DSpace on 2016-09-27T23:24:47Z (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.

Submitted by Reginaldo Soares de Freitas (reginaldo.freitas@ufv.br) on 2016-08-30T11:54:54Z No. of bitstreams: 1 texto completo.pdf: 17704467 bytes, checksum: 3fff70ad8c6dec633832a9b489d49f79 (MD5) / Made available in DSpace on 2016-08-30T11:54:54Z (GMT). No. of bitstreams: 1 texto completo.pdf: 17704467 bytes, checksum: 3fff70ad8c6dec633832a9b489d49f79 (MD5) Previous issue date: 2015-12-04 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / A proposta aqui apresentada pretende estudar, do ponto de vista global, aplicações de 3-variedades fechadas no R3 , com grafos associados ao conjunto singular destas aplicações que servem como invariantes topológicos na classificação destas e também como ferramenta para a construção de aplicações. / The proposal presented here wants to study, from a global point of view, applications of 3-manifolds closed in R3 associating graphs the single set of these applications that serves as topological invariant in the classification of these as well as a tool for building applications. / O autor não apresentou título em inglês.

Neste trabalho, apresentamos um algoritmo que determina o número de autovalores de uma matriz simétrica qualquer que representa uma árvore, num dado intervalo real. Várias aplicações são obtidas em relação à distribuição dos autovalores da matriz laplaciana perturbada, uma matriz de representação de grafos que inclui, como casos particulares, a matriz de adjacências, a matriz laplaciana combinatória, a matriz laplaciana sem sinal e a matriz laplaciana normalizada, amplamente estudadas em Teoria Espectral de Grafos. Além disso, desenvolvemos também um algoritmo de localização de autovalores da matriz de adjacências de um grafo unicíclico. Este procedimento permite obter propriedades espectrais de grafos unicíclicos denominados centopeias unicíclicas. / In this work, we present an algorithm that computes the number of eigenvalues of any symmetric matrix that represents a tree, in a given real interval. Several applications are obtained about the distribution of the eigenvalues of the perturbed Laplacian matrix, which is a matrix representation of graphs that includes, as special cases, the adjacency matrix, the combinatorial Laplacian matrix, the signless Laplacian matrix and the normalized Laplacian matrix, widely studied in Spectral Graph Theory. In addition, we also develop an algorithm that locates the eigenvalues of the adjacency matrix of a unicyclic graph. This procedure allows us to obtain spectral properties of unicyclic caterpillars.

OPERTI, Felipe Gioachino. Interpolation strategy based on Dynamic Time Warping. 2015. 53 f. Dissertação (Mestrado em Física) - Programa de Pós-Graduação em Física, Departamento de Física, Centro de Ciências, Universidade Federal do Ceará, Fortaleza, 2015. / Submitted by Edvander Pires (edvanderpires@gmail.com) on 2015-04-14T22:11:14Z No. of bitstreams: 1 2015_dis_fgoperti.pdf: 5361657 bytes, checksum: b47dae9c4d72accf5fe2c50b89abaae4 (MD5) / Approved for entry into archive by Edvander Pires(edvanderpires@gmail.com) on 2015-04-16T18:35:49Z (GMT) No. of bitstreams: 1 2015_dis_fgoperti.pdf: 5361657 bytes, checksum: b47dae9c4d72accf5fe2c50b89abaae4 (MD5) / Made available in DSpace on 2015-04-16T18:35:49Z (GMT). No. of bitstreams: 1 2015_dis_fgoperti.pdf: 5361657 bytes, checksum: b47dae9c4d72accf5fe2c50b89abaae4 (MD5) Previous issue date: 2015 / In oil industry, it is essential to have the knowledge of the stratified rocks’ lithology and, as consequence, where are placed the oil and the natural gases reserves, in order to efficiently drill the soil, without a major expense. In this context, the analysis of seismological data is highly relevant for the extraction of such hydrocarbons, producing predictions of profiles through reflection of mechanical waves in the soil. The image of the seismic mapping produced by wave refraction and reflection into the soil can be analysed to find geological formations of interest. In 1978, H. Sakoe et al. defined a model called Dynamic Time Warping (DTW)[23] for the local detection of similarity between two time series. We apply the Dynamic Time Warping Interpolation (DTWI) strategy to interpolate and simulate a seismic landscape formed by 129 depth-dependent sequences of length 201 using different values of known sequences m, where m = 2, 3, 5, 9, 17, 33, 65. For comparison, we done the same operation of interpolation using a Standard Linear Interpolation (SLI). Results show that the DTWI strategy works better than the SLI when m = 3, 5, 9, 17, or rather when distance between the known series has the same order size of the soil layers.

SILVA, Aline Alves da. Decomposição e largura em árvore de grafos planares livres de ciclos pares induzidos. 2007. 71 f. : Dissertação (mestrado) - Universidade Federal do Ceará, Departamento de Computação, Fortaleza-CE, 2007. / Submitted by guaracy araujo (guaraa3355@gmail.com) on 2016-05-20T19:42:38Z No. of bitstreams: 1 2007_dis_aasilva.pdf: 635256 bytes, checksum: 0ac10f7ac58ad14294969b2e4a830ce0 (MD5) / Approved for entry into archive by guaracy araujo (guaraa3355@gmail.com) on 2016-05-20T19:43:21Z (GMT) No. of bitstreams: 1 2007_dis_aasilva.pdf: 635256 bytes, checksum: 0ac10f7ac58ad14294969b2e4a830ce0 (MD5) / Made available in DSpace on 2016-05-20T19:43:21Z (GMT). No. of bitstreams: 1 2007_dis_aasilva.pdf: 635256 bytes, checksum: 0ac10f7ac58ad14294969b2e4a830ce0 (MD5) Previous issue date: 2007 / The definitions of tree decomposition and treewidth were introduced by Robertson and Seymour in their series of papers on graph minors, published during the nineties. It is known that many NP-hard problems can be polynomially solved if a tree decomposition of bounded treewidth is given. So, it is of interest to bound the treewidth of certain classes of graphs. In this context, the planar graphs seem to be specially challenging because, in despite of having many known bounded metrics (for example, chromatic number), they have unbounded treewidth. So, an alternative approach is to restrict ourselves to a subclass of planar graphs. In this work, we investigate the class of even-hole-free planar graphs. We show that if G is an even-hole-free planar graph, then it does not contain a subdivision of the 10£10 grid. So, if the grid minors of G are obtained from subdivisions, then G has treewidth at most 49. Furthermore, two polynomial, non-exact algorithms to compute a tree decomposition of a even-hole-free planar graph are given, both based on known characterizations of even-hole-free graphs. In the ¯rst one, a tree decomposition is built from basic graphs by concatenating the tree decomposition of small pieces via the clique, k-stars (k = 1; 2; 3) and 2-join cutsets. In the second one, a tree decomposition is built by including one by one the vertices of G, following their bi-simplicial order. / Os conceitos de Decomposição em Árvore e Largura em Árvore foram introduzidos por Robertson e Seymour em sua série de artigos sobre menores de grafos, publicados ao longo da década de 90. Sabe-se que muitos problemas NP - difíceis podem ser resolvidos polinomialmente para um grafo G, dada uma decomposição em Árvore de G de largura limitada. Logo, limitar a largura em árvore de uma classe de grafos torna-se um objeto de estudo de grande interesse. Neste contexto, a classe dos grafos planares se mostra bastante intrigante, uma vez que, apesar de possuir outras métricas limitadas em valores baixos (por exemplo, número cromático), não possui largura em árvore limitada. Desta forma, uma alternativa é restringir a classe estudada para uma subclasse dos grafos planares. Neste trabalho, nós investigamos a classe dos grafos planares livres de buracos pares. Nós mostramos que se G é um grafo planar livre de buracos pares, então ele não contém uma subdivisão de uma grade 10 £ 10. Portanto, se os menores grades de G são obtidos de subdivisões G tem largura em árvore no máximo 49. Além disso, dois algoritmos não exatos polinomiais para computar uma decomposição em árvore de um grafo planar livre de buracos pares são apresentados, ambos baseados em caracterizações conhecidas de tal classe de grafos. No primeiro algoritmo, uma decomposição em árvore é construída a partir de grafos básicos pela concatenação de decomposições em árvores de pedaços pequenos via os cortes clique, k-estrelas (k = 1; 2; 3) e 2-join. No segundo, uma decomposição em árvore é construída pela inclusão dos vértices de G um a um, seguindo sua ordem bi-simplicial.

Orientador: Prof. Dr. Letícia Rodrigues Bueno / Dissertação (mestrado) - Universidade Federal do ABC, Programa de Pós-Graduação em Ciência da Computação, 2015. / Given a graph G, the hamiltonian cycle problem consists in determining if there is a cycle containing all vertices of G exactly once. This problem is known to be NP-Complete, therefore a recent trend is to searching for long cycles in order to determine the cycle with the largest possible number of vertices. Another trend is searching for related structures. In this aspect, being prism-hamiltonian has been an interesting relaxation of being hamiltonian. The prism over a graph G consists of two copies of G with an edge joining the corresponding vertices. A graph G is prism-hamiltonian if the prism over G contains a hamiltonian cycle. In this work, we study a conjecture which claims that every 4-connected 4-regular graph is prism-hamiltonian. We prove the conjecture for claw-free graphs. In fact, for a subclass of claw-free 4-connected 4-regular graphs, we prove a stronger result: its hamiltonicity; therefore, corroborating to another conjecture from 1993 which states that claw-free 4-connected 4-regular graphs are hamiltonian. Given a graph G, let G1 = GK2 and Gq = Gq..1K2, for q > 1. For every connected graph G, we prove that Gq is hamiltonian for q dlog2 (G)e, where (G) is the maximum degree of G.

Dissertação (mestrado) - Universidade Federal de Santa Catarina, Centro Tecnológico. Programa de Pós-Graduação em Engenharia de Produção. / Made available in DSpace on 2012-10-21T11:16:53Z (GMT). No. of bitstreams: 1 214048.pdf: 2531808 bytes, checksum: b4579a715576cd7603a6b3238f14bd5e (MD5) / O conhecimento tem se configurado como um recurso estratégico nas organizações. Para elas, gerar, codificar, gerir e disseminar o conhecimento organizacional tornaram-se tarefas essenciais. Logo, é necessário o desenvolvimento de novas técnicas, metodologias e formas de extração de conhecimento a partir de fontes de informação que descrevem um domínio de aplicação. Nesse contexto, o objetivo do presente trabalho é propor um método que permita traduzir fontes de informação em um formato padrão de representação de relacionamentos entre elementos do domínio do problema, de forma a viabilizar a extração de conhecimento por meio da aplicação de Link Analysis e Teoria dos Grafos. Além disso, são apresentadas duas aplicações desse modelo na Plataforma Lattes de CT&I.

Orientador : Prof. Dr. Arinei Carlos Lindbeck da Silva / Tese (doutorado) - Universidade Federal do Paraná, Setor de Tecnologia, Programa de Pós-Graduação em Métodos Numéricos em Engenharia. Defesa: Curitiba, 12/09/2014 / Inclui referências / Resumo: Dentre os problemas de Pesquisa Operacional, o Problema de Transporte (PT) é destacado como um dos mais importantes, devido a sua estrutura especial e, principalmente, pelas aplicações que não se limitam a problemas de distribuição. Para a resolução do Problema de Transporte, é amplamente conhecido na literatura e utilizado o método MODI, no qual são calculadas as variáveis duais e com base nelas recalculados os valores dos custos atualizados e que apresenta economia de tempo para resolução em relação ao método Stepping Stone. Na presente tese, a resolução do PT pelo método MODI foi realizada por uma implementação utilizando estrutura de quadro para armazenamento de informações e outra de árvore, sendo concluído que a resolução em árvore gerou uma economia média de 60,24% de tempo em relação à resolução em quadro. Foi demonstrado, sem a utilização das variáveis duais, que é possível o recálculo dos custos atualizados somente em função dos custos atualizados da iteração anterior e com a implementação deste resultado houve redução de 80,78% no tempo de resolução em relação à implementação do método MODI em árvore. Desta forma, a redução média da implementação em árvore recalculando somente os custos atualizados necessários foi de 92,34% em relação à implementação em quadro. Para reduzir ainda mais o tempo de resolução foi proposta uma nova forma de critério para escolha da variável não básica a entrar na base, utilizando uma lista, denominada ReferenciaCAN, menor de variáveis candidatas a tornarem-se básica na iteração e também um parâmetro, denominado PercentualEconomiaAnterior, para evitar a seleção de variáveis não básicas que não gerassem uma economia unitária menor que a desejada. Com isso foi possível reduzir o tempo médio de resolução em 37,06% em relação a situação anterior. De forma final, o tempo de resolução para o método e implementação final proposto na presente tese obteve uma redução de 95,18% em relação ao tempo médio da implementação clássica do método MODI em quadro. Palavras-chave: Problema de Transporte, método MODI, melhoria de solução, recálculo de custos atualizados, implementação computacional. / Abstract: Among the Operational Research problems, the Transportation Problem (TP) is highlighted as one of the most important, due to its special structure, and especially by applications that are not limited to distribution problems. In order to solve the Transportation Problem, it is widely known in the literature and used the MODI method, in which the dual variables are calculated and based on them the reduced costs are recalculated, providing time saving when compared to the Stepping Stone method. In this thesis, the PT solver by MODI method was performed by using an implementation in the tableau structure for storing information and other using tree structure. It was concluded that when the problems were solved using tree structure it was generated an average savings of 60.24% of time in comparison to tableau structure. Therefore, it was demonstrated without the use of the dual variables, that it is possible recalculation of reduced costs only considering reduced costs of the previous iteration and the implementation of this rule resulted in 80.78% reduction in time to solve when compared to the implementation of the method MODI using tree structure. Thus, the average reduction in tree implementation recalculating only the updated costs required was 92.34% in relation to the implementation in tableau structure. In order to reduce again the time a new way has been proposed as criteria for the choice of the non basic variable to enter the basis, using a list, called ReferenciaCAN, with fewer variables candidates to become basic at current iteration and also a parameter, called PercentualEconomiaAnterior, to avoid the selection of non-basic variables that do not generate a smaller unitary economy than desired. It was then possible to reduce the average resolution time by 37.06% compared to the previous situation. After the modifications, the solver time for the final implementation and method proposed in this thesis achieved a reduction of 95.18% compared to the average time the classical implementation of MODI method in tableau structure. Keywords: Transportation Problem, MODI method, solution improvement, reduced costs computing, computational implementation.

Made available in DSpace on 2016-06-02T20:06:00Z (GMT). No. of bitstreams: 1 1882.pdf: 2136275 bytes, checksum: 88195acab4700b3e71382c38ec0dd827 (MD5) Previous issue date: 2008-06-27 / Financiadora de Estudos e Projetos / The purpose of this work is to examine statistical methodologies that can be applied to problems that involve a large number of variables using as a tool graphical models that assist on the visualization of the conditional independency and dependency structure, thus a graphical model represents the relationship between random variables (dependence, independence and conditional independence), each node is a random variable and the edges between the nodes are different ways they relate to each other. This dissertation studies Gaussian graphical models. We use methodologies for large scale models (\large p and small n") used on the analysis of gene association from gene expression data. We describe the sparse graphical models and we implement a computational algorithm. We veriffed a Bayesian approach using the Reversible Jump MCMC. We also introduce decomposable graphical models in relation to the computational effciency attained by the decomposition of the sample space, and we found the best decomposable graph based on the Metropolis-Hastings algorithm for a real data set. / Neste trabalho temos como objetivo verificar metodologias estatísticas que podem ser aplicadas a problemas que envolvem um grande número de variáveis, utilizando para isto modelos grafos, que auxiliam na visualização da estrutura de dependência e independência condicional, portanto um modelo grafo representa a relação entre variáveis aleatórias (dependência, independência e independência condicional), onde cada vértice é uma variável aleatória e as arestas entre os vértices representam as diferentes formas de relação entre as variáveis. Nesta dissertação trabalhamos com modelos grafos Gaussianos. Abordamos metodologias para modelos de grande escala (\p grande, n pequeno") voltadas para análise de associações entre genes, utilizando dados de expressão gênica. Descrevemos os modelos grafos esparsos e implementamos um algoritmo computacional. Verificamos uma abordagem bayesiana usando Reversible Jump MCMC. Apresentamos também os modelos grafos decomponíveis quanto a eficiência computacional obtida a partir da decomposição dos espaços amostrais, e encontramos o melhor grafo decomponível baseado no algoritmo de Metropolis-Hastings para um conjunto de dados reais.

Made available in DSpace on 2014-08-13T14:50:59Z (GMT). No. of bitstreams: 0 Previous issue date: 2014-03-31Bitstream added on 2014-08-13T17:59:48Z : No. of bitstreams: 1 000773520.pdf: 599821 bytes, checksum: 0341b612274b313baef13dc8cdb71c59 (MD5) / O objetivo deste trabalho é apresentar alguns resultados elementares de Álgebra Linear e relacioná-los com a Teoria de Grafos, por meio de exemplos, sempre que possível. A ferramenta básica para isso é a teoria de matrizes / The aim of this work is to present some elementary results from Linear Algebra and to relate them with Graph Theory, making use of examples if possible