Orientador: Jose Carlos de Souza Kiihl / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Computação Cientifica / Made available in DSpace on 2018-07-23T20:43:57Z (GMT). No. of bitstreams: 1 LaGuardia_GiulianoGadioli_M.pdf: 613779 bytes, checksum: 83afd407174483ae4bd9e82d87d56a26 (MD5) Previous issue date: 1998 / Resumo: Não informado. / Abstract: Not informed. / Mestrado / Mestre em Matemática

Orientador: Claudio Leonardo Luchesi / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Computação Científica / Made available in DSpace on 2018-07-15T14:08:34Z (GMT). No. of bitstreams: 1 Stavropoulou_IaraCiurria_M.pdf: 1494745 bytes, checksum: 382758638b7993a24d5c291c8e4e0423 (MD5) Previous issue date: 1982 / Resumo: É apresentada uma condição necessária e suficiente para que um grafo finito possua um subgrafo gerador em que cada vértice tenha seu grau num intervalo especificado. Este resultado generaliza outros obtidos por Hall e Tutte em que o intervalo de cada vértice é reduzido a um ponto. A demonstração é construtiva, e obtém-se um algoritmo polinomial que determina um subgrafo que mais se aproxima num sentido bem definido, das especificações desejadas. Mostra-se ainda que ao se atribuir pesos às arestas, o problema se torna estão NP-completo.São apresentadas também algumas aplicações elementares do teorema, as quais incluem fluxos em redes e seqüências gráficas. / Abstract: A necessary and sufficient condition for a finite graph to have spanning subgraph in which the degree of each vertex lies in a specified interval is presented. This result generalizes others that were obtained by Hall and Tutte, in which the interval of each vertex is reduced to a single point. The proof is constructive and a polinomial algorithm is obtained. This algorithm determines a subgraph which in a well defined sense, is as close as possible to the desired specifications. It is shown that when we associate weights with the edges, the problem becomes NP-complete. Some direct applications of the theorem are also presented which include flows in networks and graphic sequences. / Mestrado / Mestre em Matemática Aplicada

Resumo não disponível

A presente tese de doutorado trata de problemas de coloração de hipergrafos. Mais precisamente, nós trabalhamos com o chamado Problema de Erdos e Rothschild no caso de colorações arco- ris de hipergrafos. Nossas contribuições envolvem os hipergrafos plano de Fano (hipergrafo 3-uniforme com 7 v ertices e 7 hiperarestas onde todo par de v ertices e coberto) e K(k) +1 (hipergrafo obtido do grafo K+1 onde cada aresta recebe k 2 novos v ertices). Para F 2 fFano;K(k) +1g, encontramos o hipergrafo k-uniforme com o maior n umero de r-colorações de hiperarestas que não contêm cópia de F com a propriedade de que todas as suas hiperarestas têm cores distintas. Como ferramentas para tais demonstrações, obtivemos resultados mais precisos de estabilidade para K(k) +1 e outros hipergrafos ou famílias de hipergrafos, bem como um resultados de estabilidade para colorações para uma classe de hipergrafos lineares, que contém Fano e K(k)+1. Para os resultados de estabilidade para colorações utilizamos o Lema de Regularidade, introduzido por Szemeredi no contexto de grafos, e o Lema de Imersão, ambos considerados mais tarde para hipergrafos lineares por Kohayakawa, Nagle, Rodl e Schacht. / In this thesis we consider problems about colorings of hypergraphs. More precisely, we deal with the so-called Erd}os and Rothschild Problem in the case of rainbow colorings of hypergraphs. Our contributions involve the hypergraphs Fano plane (the 3-uniform hypergraph on 7 vertices and 7 hyperedges where every pair of vertices is covered) and K(k) `+1 (the hypergraph obtained from K`+1 where each edge is enlarged by k 2 new vertices). For F 2 fFano;K(k) `+1g, we obtained the k-uniform hypergraph with the largest number of r-colorings of hyperedgees not containing a copy of F with the property that all hyperedges are colored di erently. As a tool for such proofs, we obtained a sharper stability result for K(k) `+1 and other hypergraphs and families of hypergrahs. We also obtained a color stability result for a class of linear hypergraphs, which contains Fano and K(k) `+1. For these color stability result we used the Regularity Lemma, originally stated by Szemer edi for graphs, and the Embedding Lemma, both considered later for linear hypergraphs by Kohayakawa, Nagle, Rodl and Schacht

El objetivo de esta tesis ha sido diseñar nuevos algoritmos en el campo del análisis de observabilidad de procesos industria-les empleando teoría de grafos y conceptos avanzados de ciencias de la computación. Como resultado de estas inves-tigaciones se ha logrado el desarrollo de técnicas robustas y eficientes especialmente diseñadas para la clasificación de variables no medidas en procesos industriales con modelos matemáticos fuertemente no lineales. Mediante el empleo de los nuevos algoritmos propuestos en esta tesis ahora es posible el tratamiento en forma precisa y eficiente de proble-mas que no podían ser resueltos por los métodos de observabi-lidad clásicos, o que requerían una estricta simplificación de su modelo matemático para que estas técnicas pudieran ser aplicadas. Los métodos desarrollados se basan fundamental-mente en la permutación de la matriz de ocurrencia correspon-diente al sistema de ecuaciones que modela la planta. Estos reordenamientos estructurales emplean técnicas de descompo-sición de grafos, digrafos, bigrafos e hipergrafos. Todas las técnicas desarrolladas lograron un muy buen desempeño, res-pecto de las metodologías existentes, al ser empleadas en la clasificación de variables no medidas de modelos matemáticos complejos correspondientes a problemas industriales reales. Finalmente, se diseñó e implementó un sistema de soporte de decisión que engloba toda la experiencia adquirida en clasifi-cación de variables a lo largo de este trabajo de tesis. El software desarrollado resulta eficiente, robusto y amigable, asistiendo al usuario en forma versátil y confiable en la com-pleja tarea de establecer la ubicación más apropiada para los sensores que controlan el correcto funcionamiento de una planta real. El paquete posibilita analizar en forma rigurosa plantas de cualquier dimensión, incluso las de gran enver-gadura.

Ingeniero Civil Matemático / El objetivo principal de esta memoria es estudiar generalizaciones del problema de emparejamientos en línea. En un artículo seminal Karp, Vazirani y Vazirani estudiaron el siguiente problema de optimización: Dado un grafo bipartito G=(L,R,E) del que el lado L es conocido y el lado R llega en línea, se busca maximizar el tamaño de un emparejamiento, bajo la condición de que solo se puede emparejar un vértice en el momento en el que llega. Karp, Vazirani y Vazirani encuentran un algoritmo que es una (1-1/e)-aproximación para el problema. En esta memoria se generaliza el problema al caso en el que un lado no está fijo, o sea que vértices de ambos lados pueden llegar en línea. Se estudian tres modelos: el modelo adversarial, el modelo de orden aleatorio y el modelo fuera de línea. Para el modelo adversarial se definen algoritmos locales y se demuestra que ninguno de ellos puede ser mejor que una 1/2-aproximación. Para el modelo de orden aleatorio se encuentra un algoritmo cuya competividad está en el intervalo [0.696, 0.727]. Finalmente, para el modelo fuera de línea se encuentra un algoritmo óptimo cuya competividad es desconocida, pero se demuestra que está en el intervalo [0.526, 0.591].

O problema de particionamento balanceado de grafos consiste em encontrar uma partição de tamanho k dos vértices de um grafo, minimizando o número de arestas que participam do corte tal que o tamanho de nenhuma parte exceda [en~k], para algum e e > [1, k). Essa dissertação estuda esse problema, apresentando uma revisão recente de heurísticas construtivas, heurísticas de refinamento e técnicas multinível. Também propomos um novo algoritmo híbrido para resolver esse problema de particionamento. Nós mostramos como diversas estratégias para construir e aprimorar partições, assim como algumas novas propostas, podem ser integradas para formar um GRASP com path-relinking. Reportamos experimentos computacionais que mostram que essa abordagem obtém soluções competitivas com particionadores no estado-da-arte. Em particular, o algoritmo híbrido é capaz de encontrar novos melhores valores conhecidos em algumas das menores instâncias, indicando que tem uma contribuição qualitativa comparado aos métodos existentes. / The balanced graph partitioning problem asks to find a k-partition of the vertex set of an undirected graph, which minimizes the total cut size and such that the size of no part exceeds en/k , for some ee > [1, k]. This dissertation studies this problem, providing a recent review of constructive heuristics, refinement heuristics and multilevel techniques. We also propose a new hybrid algorithm for solving this partitioning problem. We show how several good existing strategies for constructing and improving partitions, as well as some newly proposed ones, can be integrated to form a GRASP with path-relinking. We report computational experiments that show that this approach obtains solutions competitive with state-of-the-art partitioners. In particular, the hybrid algorithm is able to find new best known values in some of the smaller instances, indicating that it can make a qualitative contribution compared to existing methods.

Dissertação (mestrado) - Universidade Federal de Santa Catarina. Centro Tecnologico / Made available in DSpace on 2016-01-08T15:39:56Z (GMT). No. of bitstreams: 1 82967.pdf: 5887865 bytes, checksum: 4125e0165ec77609d74b1306dc2f0ce5 (MD5) Previous issue date: 1987 / O presente trabalho tem por objetivo realizar uma análise comparativa entre dois algoritmos que determinam um caminho de mínimo custo, entre um vértice inicial e um vértice final especificados de um grafo com custos não-negativos. Inicialmente é feito um estudo desses algoritmos, bem como suas apresentações. Posteriormente é apresentada uma análise comparativa quanto ao desempenho computacional dos mesmos. Finalmente são relacionados os problemas estudados e um exemplo ilustra cada procedimento.

O problema de particionamento balanceado de grafos consiste em encontrar uma partição de tamanho k dos vértices de um grafo, minimizando o número de arestas que participam do corte tal que o tamanho de nenhuma parte exceda [en~k], para algum e e > [1, k). Essa dissertação estuda esse problema, apresentando uma revisão recente de heurísticas construtivas, heurísticas de refinamento e técnicas multinível. Também propomos um novo algoritmo híbrido para resolver esse problema de particionamento. Nós mostramos como diversas estratégias para construir e aprimorar partições, assim como algumas novas propostas, podem ser integradas para formar um GRASP com path-relinking. Reportamos experimentos computacionais que mostram que essa abordagem obtém soluções competitivas com particionadores no estado-da-arte. Em particular, o algoritmo híbrido é capaz de encontrar novos melhores valores conhecidos em algumas das menores instâncias, indicando que tem uma contribuição qualitativa comparado aos métodos existentes. / The balanced graph partitioning problem asks to find a k-partition of the vertex set of an undirected graph, which minimizes the total cut size and such that the size of no part exceeds en/k , for some ee > [1, k]. This dissertation studies this problem, providing a recent review of constructive heuristics, refinement heuristics and multilevel techniques. We also propose a new hybrid algorithm for solving this partitioning problem. We show how several good existing strategies for constructing and improving partitions, as well as some newly proposed ones, can be integrated to form a GRASP with path-relinking. We report computational experiments that show that this approach obtains solutions competitive with state-of-the-art partitioners. In particular, the hybrid algorithm is able to find new best known values in some of the smaller instances, indicating that it can make a qualitative contribution compared to existing methods.

O problema de particionamento balanceado de grafos consiste em encontrar uma partição de tamanho k dos vértices de um grafo, minimizando o número de arestas que participam do corte tal que o tamanho de nenhuma parte exceda [en~k], para algum e e > [1, k). Essa dissertação estuda esse problema, apresentando uma revisão recente de heurísticas construtivas, heurísticas de refinamento e técnicas multinível. Também propomos um novo algoritmo híbrido para resolver esse problema de particionamento. Nós mostramos como diversas estratégias para construir e aprimorar partições, assim como algumas novas propostas, podem ser integradas para formar um GRASP com path-relinking. Reportamos experimentos computacionais que mostram que essa abordagem obtém soluções competitivas com particionadores no estado-da-arte. Em particular, o algoritmo híbrido é capaz de encontrar novos melhores valores conhecidos em algumas das menores instâncias, indicando que tem uma contribuição qualitativa comparado aos métodos existentes. / The balanced graph partitioning problem asks to find a k-partition of the vertex set of an undirected graph, which minimizes the total cut size and such that the size of no part exceeds en/k , for some ee > [1, k]. This dissertation studies this problem, providing a recent review of constructive heuristics, refinement heuristics and multilevel techniques. We also propose a new hybrid algorithm for solving this partitioning problem. We show how several good existing strategies for constructing and improving partitions, as well as some newly proposed ones, can be integrated to form a GRASP with path-relinking. We report computational experiments that show that this approach obtains solutions competitive with state-of-the-art partitioners. In particular, the hybrid algorithm is able to find new best known values in some of the smaller instances, indicating that it can make a qualitative contribution compared to existing methods.