Orientador : Prof. Dr. Elias P. Duarte Jr. / Co-orientador : Prof. Dr. Jaime Cohen / Dissertação (mestrado) - Universidade Federal do Paraná, Setor de Ciências Exatas, Programa de Pós-Graduação em Informática. Defesa: Curitiba, 14/12/2015 / Inclui referências : f. 46-48 / Resumo: As árvores de cortes representam, de forma compacta, a aresta conectividade entre todos os pares de vértices de um grafo com pesos nas arestas. Existem muitas aplicações de arvores de cortes como, por exemplo, em projetos de redes confiáveis, partição de grafos, analise de redes, segmentação de imagens entre outras. Dois algoritmos clássicos para construção de arvores de cortes são conhecidos: o algoritmo de Gomory-Hu e o algoritmo de Gusfield. Neste trabalho sao apresentadas versões paralelas de um dos algoritmos clássicos para a construção de árvores de cortes, o algoritmo de Gomory-Hu. Este al-goritmo faz máltiplas chamadas a um procedimento que encontra um corte de arestas de capacidade mínima entre dois vértices. Para encontrar os cortes mínimos, o algoritmo faz contrações de vértices do grafo de entrada. O procedimento para construção do grafo contraído e custoso e implementá-lo de forma eficiente não e trivial. Portanto e importante investigar pontos que podem ser otimizados nesse procedimento. A principal contribuição deste trabalho e a especificação de uma estratégia paralela baseada no modelo mestre-escravo que permite que processos aproveitem instâncias de grafos contraídos de passos anteriores. A otimização tem o objetivo de viabilizar uma forma eficiente de realizar as operações de contração nos processos escravos, já que estes sempre calculam o grafo contraído sobre o mesmo grafo. De forma geral, a implementação dessa otimização requer que o processo mestre tenha controle sobre as tarefas que foram enviadas para cada escravo, armazenando-as para que sejam utilizadas quando as respostas chegarem. Os processos escravos, por sua vez, precisam tomar decisões sobre quando aproveitar ou não, uma instância de grafo contraído. E também apresentada a aplicação da otimização proposta para um algoritmo híbrido que combina características do algoritmo de Gomory- Hu e do algoritmo de Gusfield, também baseado em contrações otimizadas. Para avaliar a eficiência desta versão foram realizados experimentos em um cluster de alto desempenho. Foram realizados testes de speedup e comparativos entre as versões paralelas existentes. Foram realizados também, experimentos com uma implementação do algoritmo paralelo de Gomory-Hu utilizando o conjunto de bibliotecas Boost para avaliar o desempenho de diferentes algoritmos de fluxo máximo (utilizados para calcular os s-t cortes mínimos). / Abstract: Cut trees represent the edge-connectivity between all pairs of nodes of an undirected weighted graph. There are many cut tree applications, such as the design of reliable networks, graph partitioning, network analysis, image segmentation, among others. Two classical algorithms that solve the problem of finding a cut tree of an undirected weighted graph are known: the Gomory-Hu algorithm and the Gusfield algorithm. This work presents parallel versions of the Gomory-Hu algorithm. This algorithm makes multiple calls to a procedure which finds a cut with minimum capacity between a pair of vertices. At each step the algorithm apply contractions on the input graph. The contraction procedure is costly and its implementation is not trivial. Therefore it is important to investigate ways to optimize that procedure. Previous implementations of the algorithm build the contracted graph from the input graph. The main contribution of this work is the specification of a parallel strategy that allows processes to take advantage of instances of contracted graphs from previous steps. The optimization requires the master process to have control over the tasks that were sent to each slave, storing them so they are used when the answers arrive. The slave processes, in turn, must make decisions about when to use or not a contracted graph instance. It is also shown the application of the proposed optimization in a hybrid algorithm that combines features from Gomory-Hu and Gusfield algorithms. To evaluate the efficiency of the algorithms, experiments were performed on a high performance computer cluster. Speedups and comparison tests were performed against previous parallel implementations. Experiments were also carried out with an implementation of a parallel version of Gomory-Hu algorithm using Boost library to evaluate the performance of different maximum flow algorithms used to compute the minimum s-t cuts.

Orientador : Renato Carmo / Dissertação (mestrado) - Universidade Federal do Paraná, Setor de Ciências Exatas, Programa de Pós-Graduação em Informática. Defesa: Curitiba, 21/08/2017 / Inclui referências : p. 81-83 / Resumo: O problema de coloração de grafos consiste em particionar os vértices de um grafo na menor quantidade possível de conjuntos independentes. Este trabalho tem como objetivo agrupar e contextualizar alguns dos principais algoritmos para o problema de coloração de grafos, reunindo num mesmo texto informações que se encontram espalhadas pela literatura técnica sob a forma de artigos científicos. Discutimos os principais métodos apresentados na literatura para o problema de coloração de grafos, a saber, soluções baseadas em Programação Linear Inteira, Branch-and-Bound e Programação Dinâmica. Palavras-chave: Teoria dos Grafos, Coloração de Grafos, Algoritmos Exatos. / Abstract: The graph coloring problem is the problem of partitioning the vertices of a graph into the smallest possible set of independent sets. The goal of this work is to group and contextualize some of the main algorithms for the graph coloring problem, bringing into a single text information which is scattered in the technical literature in scientific papers. We discuss the main methods in the literature for the graph coloring problem, namely, solutions based on Integer Linear Programming, Branch-and-Bound and Dynamic Programming. Keywords: Graph Theory, Graph Coloring, Exact Algorithms.

Made available in DSpace on 2015-05-14T16:52:58Z (GMT). No. of bitstreams: 0 Previous issue date: 2014-12-12Bitstream added on 2015-05-14T16:59:37Z : No. of bitstreams: 1 000829398.pdf: 735180 bytes, checksum: 47660f344914d561b93a77ad264e4c4b (MD5) / O objetivo principal deste trabalho é obter um resultado sobre separação de superficies por grafos. A Homologia Relativa é a principal ferramenta usada, obtendo uma versão particular da Dualidade de Lefschetz. Para a elaboração desta dissertação foram estudados: grafos, homologia simplicial, homologia relativa e grafos em superficies. O estudo foi baseado em grande parte no livro Graphs, Surfaces and Homology de P. J. Giblin / The main goal of this work is to get a result on separation of surfaces by graphs. The Relative Homology is the principal tool used and we get a particular version of Lefschetz duality. For the preparation of this dissertation we studied: graphs, simplicial homology, relative homology and graphs on surfaces. The study was based on the book Graphs, Surfaces and Homology of P. J. Giblin

Resumo: As redes complexas foram propostas para modelar qualquer sistema que possua várias partes discretas que interajam entre si. Devido a essa generalidade elas são aplicadas a diversas áreas do conhecimento. Em redes complexas existe a necessidade de utilizar diversas medidas para analisar as propriedades da rede sob diferentes aspectos. Neste trabalho apresentamos as medidas de conectividade baseadas em cortes de vértices aplicadas a redes complexas. Essas medidas identicam os nodos importantes em uma rede de acordo com a conectividade dos mesmos em relação aos demais nodos. Mostramos como calcular o valor da medida que chamamos de vértice-conectividade dos nodos. O valor da vértice-conectividade se comparado com outras medidas como grau de intermediação, grau de proximidade, excentricidade, grau e as medidas de conectividade baseadas em cortes de arestas. Foram realizadas simulações em redes sintéticas aleatórias e redes reais. As medidas foram também analisadas em casos extremos.

Orientador: Alice Kimie Miwa Libardi / Banca: Thiago de Melo / Banca: Flávia Souza Machado da Silva / Resumo: O objetivo principal deste trabalho é obter um resultado sobre separação de superficies por grafos. A Homologia Relativa é a principal ferramenta usada, obtendo uma versão particular da Dualidade de Lefschetz. Para a elaboração desta dissertação foram estudados: grafos, homologia simplicial, homologia relativa e grafos em superficies. O estudo foi baseado em grande parte no livro Graphs, Surfaces and Homology de P. J. Giblin / Abstract: The main goal of this work is to get a result on separation of surfaces by graphs. The Relative Homology is the principal tool used and we get a particular version of Lefschetz duality. For the preparation of this dissertation we studied: graphs, simplicial homology, relative homology and graphs on surfaces. The study was based on the book Graphs, Surfaces and Homology of P. J. Giblin / Mestre

Made available in DSpace on 2014-11-29T01:02:12Z (GMT). No. of bitstreams: 1 000463003-Texto+Completo-0.pdf: 2663394 bytes, checksum: 0158a49caa9b116197cb1f3a76c44980 (MD5) Previous issue date: 2014 / Resting State functional Magnetic Resonance Imaging (rs-fMRI) provides information about the functional connectivity of brain areas. However, prior to calculating the functional connectivity of the brain, there is a choice of several preprocessing steps that need to be selected. A critical source of variation between studies arises from distinct preprocessing approaches prior to the functional connectivity analysis. Therefore, a study to examine the reliability of different methods for pre-processing data from rs-fMRI is necessary. In this study, seven preprocessing strategies were tested and the reliability was evaluated between them in Graph Theoretical (GT). The sample used in this study is from a public database and consists of control subjects. Measures of GT were calculated using different strategies, after applying a method of subdividing the brain into 190 regions of interest. The following measures were calculated: global efficiency, characteristic path length, clustering coefficient and local efficiency. The results indicate that there is a significant difference in measurements of GT depending on the preprocessing strategy selected. It was also found that noise estimation parameters are correlated with GT measures. Moreover, it is observed that the level of thresholding chosen in the connectivity matrix can affect the measurements of GT, therefore further studies regarding this topic are needed. It was concluded, based on the sample used in this work that the method of scrubbing by outliers could increase the reliability of measurements of GT and reduce dependence on the movement of the patient's head. / A Ressonância Magnética Funcional no estado de repouso (rs-fMRI, do inglês resting state functional Magnetic Resonance) permite obter informações a respeito das áreas de conectividade funcional do cérebro. Porém, a visualização dessa conectividade só é possível após aplicar uma série de etapas de processamento de imagens antes que se possa avaliar a conectividade cerebral. Considerando a limitação na quantificação dos dados de rs-fMRI, e sabendo que uma fonte de variação crítica para a comparação entre os estudos é o fato de cada um deles remover, incluir ou mudar parâmetros nos passos de pré-processamento de rs-fMRI, é necessário um estudo para analisar a confiabilidade de diferentes metodologias de préprocessamento de dados de rs-fMRI. Para tanto, a Teoria dos Grafos (TG) foi utilizada como parâmetro final para avaliar a conectividade. Neste presente trabalho, foram testadas sete estratégias de pré-processamento e foi avaliada a confiabilidade entre elas quando são feitas medidas de TG. A amostra utilizada neste trabalho é de uma base de dados pública e é composta por indivíduos controle. As medidas de TG foram calculadas nas diferentes estratégias, após aplicar um método de parcelamento do cérebro em 190 regiões. Foram calculadas as seguintes medidas: eficiência global, comprimento do caminho característico, coeficiente de agrupamento e eficiência local. Os resultados indicaram que existe uma diferença significativa nas medidas de teoria dos grafos quando o pré-processamento é feito de diferentes maneiras. Foi encontrado também que parâmetros de estimativa de ruído são correlacionados com as medidas de TG. Além disso, observa-se que o nível de limiarização escolhido na matriz de conectividade pode afetar significativamente as medidas de TG, sendo necessário um estudo mais aprofundado a respeito deste tema. Concluiu-se, baseado na amostra utilizada neste trabalho, que o método de scrubbing por outliers pode aumentar a confiabilidade das medidas de TG e reduzir a sua dependência com o movimento da cabeça do paciente.

O objetivo principal deste trabalho é apresentar uma. descrição detalhada sobre as diversas abordagens do Problema do Caixeiro Viajante, a complexidade na sua resolução e as aplicações nas diversas áreas do conhecimento. O Problema do Caixeiro Viajante é um dos mais conhecidos e estudados problemas da Teoria dos Grafos e sua importância é tanta teórica quanto prática. O resultado teórico mais importante que apresentamos neste trabalho é a prova de que o PCV é -P-Completo, usando (e provando) o Teorema de Cook, como ponto de partida e a Máquina de Turing como o modelo computacional para as provas da complexidade dos problemas envolvidos. O PCV é equivalente ao problema de encontrar um circuito Hamiltoniano de peso mínimo em um grafo ponderado. Uma das questões principais envolvidas neste problema, e na verdade uma das principais indagações da Ciência da Comput ação, é saber se existe um algoritmo eficiente de tempo polinomial para calcular tal circuito, ou se tal algoritmo não existe, caracterizando-o, assim, como um problema impossível de ser resolvido. Quando não se pode encontrar uma solução eficiente para um dado problema e também não pode ser demonstrado que tal solução existe, deve-se usar técnicas que permitam construir um algoritmo que forneça soluções aproximadas. Neste trabalho, apresentamos um algoritmo de tempo polinomial que nos fornece soluções aproximadas para o PCV. / The main objective of this work is to present a detailed description on the various approaches to the Traveling Salesperson Problem (TSP), the complexity of its solution and its applications to the various knowledge area.s. The Traveling Salesperson Problem is one of the most known and studied problems in graph theory and its importance is theoretical as well as practical. The theory result more important who we will introduce in this work is the proof of the TSP is NP-complete, using (and proving) of Cook's Theorem like point of departure and the Turing Machine like the model computational for the tests of complexity of problems involved. The TSP is equivalent to the problem of finding a Hamiltonian circuit of minimal weight in a weighted graph. One of the main questions involved in this problem, and actually one of the main questions of the whole Computing Science, is to know if there exists an polynomial-time efficient algorithm to compute such a circuit, or if such an algorithm can not exist, then characterizing it as an impossible problem. When one can not find an efficient solution for a given problem and also can not show that such a solution exists, we must use techniques that aid us to construct an algorithm providing approximate solutions. In this work, we will present a polynomial-time algorithm that gives approximate solutions for the solution of the Traveling Salesperson Problem.

O objetivo principal deste trabalho é apresentar uma. descrição detalhada sobre as diversas abordagens do Problema do Caixeiro Viajante, a complexidade na sua resolução e as aplicações nas diversas áreas do conhecimento. O Problema do Caixeiro Viajante é um dos mais conhecidos e estudados problemas da Teoria dos Grafos e sua importância é tanta teórica quanto prática. O resultado teórico mais importante que apresentamos neste trabalho é a prova de que o PCV é -P-Completo, usando (e provando) o Teorema de Cook, como ponto de partida e a Máquina de Turing como o modelo computacional para as provas da complexidade dos problemas envolvidos. O PCV é equivalente ao problema de encontrar um circuito Hamiltoniano de peso mínimo em um grafo ponderado. Uma das questões principais envolvidas neste problema, e na verdade uma das principais indagações da Ciência da Comput ação, é saber se existe um algoritmo eficiente de tempo polinomial para calcular tal circuito, ou se tal algoritmo não existe, caracterizando-o, assim, como um problema impossível de ser resolvido. Quando não se pode encontrar uma solução eficiente para um dado problema e também não pode ser demonstrado que tal solução existe, deve-se usar técnicas que permitam construir um algoritmo que forneça soluções aproximadas. Neste trabalho, apresentamos um algoritmo de tempo polinomial que nos fornece soluções aproximadas para o PCV. / The main objective of this work is to present a detailed description on the various approaches to the Traveling Salesperson Problem (TSP), the complexity of its solution and its applications to the various knowledge area.s. The Traveling Salesperson Problem is one of the most known and studied problems in graph theory and its importance is theoretical as well as practical. The theory result more important who we will introduce in this work is the proof of the TSP is NP-complete, using (and proving) of Cook's Theorem like point of departure and the Turing Machine like the model computational for the tests of complexity of problems involved. The TSP is equivalent to the problem of finding a Hamiltonian circuit of minimal weight in a weighted graph. One of the main questions involved in this problem, and actually one of the main questions of the whole Computing Science, is to know if there exists an polynomial-time efficient algorithm to compute such a circuit, or if such an algorithm can not exist, then characterizing it as an impossible problem. When one can not find an efficient solution for a given problem and also can not show that such a solution exists, we must use techniques that aid us to construct an algorithm providing approximate solutions. In this work, we will present a polynomial-time algorithm that gives approximate solutions for the solution of the Traveling Salesperson Problem.

Submitted by Victor Hugo Albuquerque Rizzo (victor.rizzo@ufpe.br) on 2015-04-14T14:55:20Z No. of bitstreams: 2 license_rdf: 1232 bytes, checksum: 66e71c371cc565284e70f40736c94386 (MD5) DISSERTAÇÃO Jônata Ferreira de Melo.pdf: 4496803 bytes, checksum: 608a870941a111c2fef5e1ad33e18180 (MD5) / Made available in DSpace on 2015-04-14T14:55:20Z (GMT). No. of bitstreams: 2 license_rdf: 1232 bytes, checksum: 66e71c371cc565284e70f40736c94386 (MD5) DISSERTAÇÃO Jônata Ferreira de Melo.pdf: 4496803 bytes, checksum: 608a870941a111c2fef5e1ad33e18180 (MD5) Previous issue date: 2013 / Este trabalho propõe a utilização da teoria dos grafos e simulação computacional para analisar redes hidráulicas industriais, isto com o intuito principal de reduzir o tempo desprendido na simulação dos cenários propostos. Esta metodologia é baseada principalmente em sete etapas: converter a rede hidráulica em um grafo correspondente, sistematizar o cálculo das perdas de carga para cada trecho; automatizar a análise do grafo no MATLAB®; analisar o resultado do ponto hidraulicamente mais desfavorável; elaborar de acordo com o ponto hidraulicamente mais desfavorável, novos cenários alterando parâmetros como diâmetro das tubulações; dimensionar bomba para os cenários viáveis e analisar o custo de cada cenário proposto. Com este método de análise as simulações dos diversos cenários puderam ser realizadas em poucos minutos. A agilidade na elaboração e decisão envolvidas na etapa de projeto é essencial para que a etapa de construção e montagem providencie os recursos com mais antecedência o que dá uma folga maior para absorver os imprevistos da construção e montagem.

Orientador: Patrícia Helena Araújo da Silva Nogueira / Dissertação (mestrado profissional) - Universidade Estadual de Campinas, Instituto de Matemática, Estatística e Computação Científica / Made available in DSpace on 2018-08-17T08:03:36Z (GMT). No. of bitstreams: 1 Staib_FredericoFontes_M.pdf: 14016255 bytes, checksum: 4ec6112a82029b5e16c1c450779bf803 (MD5) Previous issue date: 2010 / Resumo: Neste trabalho, estudamos a teoria das bases de Gröbner e sua aplicação ao problema da k-coloração de grafos, estabelecendo assim uma interessante conexão entre a álgebra abstrata e a matemática discreta. Fazemos também uma abordagem de caráter lúdico, traduzindo o passatempo chamado Sudoku em um problema de 9-coloração e utilizando a teoria apresentada para resolvê-lo através das bases de Gröbner / Abstract: In the present work, we study the Gröbner basis theory and its application on the graph k-coloring problem, establishing an interesting relation between abstract algebra and discrete mathematics. We make a ludic approach, translating the puzzle called Sudoku to a 9-coloring problem and using the given theory to solve it by the Gröbner basis / Mestrado / Algebra / Mestre em Matemática