Made available in DSpace on 2014-06-12T18:28:59Z (GMT). No. of bitstreams: 2 arquivo648_1.pdf: 827994 bytes, checksum: 5bd18eefcbed6a0d647716cdc47627b9 (MD5) license.txt: 1748 bytes, checksum: 8a4605be74aa9ea9d79846c1fba20a33 (MD5) Previous issue date: 2011 / Conselho Nacional de Desenvolvimento Científico e Tecnológico / Bixby e Cunningham relacionaram graficidade de matroides binárias 3-conexas e cocircuitos não separadores, generalizando um critério de planaridade de grafos 3-conexos de Tutte. Lemos estudou o conjunto de cocircuitos não-separadores que evita um elemento de uma matroide binária 3-conexa e conseguiu outra caracterização: M é gráfica se e só se cada elemento de M evita exatamente r (M)¡1 cocircuitos não separadores. Aqui estudamos o conjunto Y (M), dessas obstruções para graficidade, formado pelos elementos de M que evitam no mínimo r (M) cocircuitos não-separadores. Mostramos que, numa matroide binária 3-conexa existem 3 circuitos contidos em Y (M), cada qual não contido na união dos outros dois. Isso implica numa generalização do resultado de Lemos. No caso em que M não possui menor M¤(K000 3,3) ou M não é regular, conseguimos resultado muito melhor: jE(M)¡Y (M)j · 1. A demonstração desses resultados se baseia numa extensão de alguns resultados de Whittle a respeito demenores de matroide 3-conexas, que também são desenvolvido aqui: Seja M uma matroide binária e 3-conexa com um menor 3-conexo N. Suponha que r (M) ¸ r (N)Å3. Então existe um 3-coindependente I ¤ de M tal que co(M\e) é 3-conexa com menor isomorfo a N para todo e 2 I ¤. No mesmo capítulo desse teorema mostramos ainda uma versão para grafos que, porém, não se extende para matroides binárias

Orientador: João Meidanis / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-07-25T23:05:16Z (GMT). No. of bitstreams: 1 Cerqueira_FabioRibeiro_M.pdf: 3328400 bytes, checksum: b5fc969ee438ff4785221a8b86e87d7b (MD5) Previous issue date: 2000 / Mestrado / Mestre em Ciência da Computação

Orientadores: Celia Picinin de Mello, Anamaria Gomide / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-04T17:24:05Z (GMT). No. of bitstreams: 1 Almeida_SheilaMoraisde_M.pdf: 420796 bytes, checksum: 2ffdaaee7ece5527360d5a4d0a2827ff (MD5) Previous issue date: 2005 / Resumo: Uma representação PI consiste em duas retas paralelas, r e s, e triângulos com um vértice em r e um lado em s. Considere R uma representação PI. O grafo interseção de R é chamado grafo P I quando cada vértice do grafo corresponde a um triângulo de R e existe aresta entre dois vértices se, e somente se, os triângulos correspondentes se intersectam. Segundo o livro Graph Classes - a Survey (1999) [3], escrito por Brandstiidt, Le e Spinrad, os problemas de reconhecer e de caracterizar a classe dos grafos PI ainda não estão resolvidos. Essa é a principal motivação para o estudo da classe PI. Nesta dissertação, apresentamos um estudo dos grafos PI baseado nas suas relações com outras classes de grafos tais como os grafos de intervalos e permutação, que são classes amplamente conhecidas de grafos interseção, e os grafos trapezóides, que possuem uma estrutura muito semelhante à dos grafos PI. Esta dissertação é uma síntese de trabalhos existentes sobre a classe PI e apresenta novas condições necessárias e/ou suficientes para que um grafo seja PI / Abstract: A PI-representation consists of two parallellines, r and s, and triangles with one vertex on r and the other two on s. Let R be a PI-representation. The intersection graph of R is called PI graph when each vertex in the graph corresponds to a triangle in R and there exists an edge between two vertices if and only if their corresponding triangles intersect. According to the book Graph Classes - a Survey (1999) [3], by Brandstiidt, Le and Spinrad, the PI graph characterization and recognition problems are still open. This is the main motivation for the study of the PI graph class. In this dissertation, we present a study of PI graphs based on their relationship with other graph classes such as the interval and permutation graphs, which are well known intersection graph classes, and trapezoid graphs, which have a very similar structure to that of PI graphs. This dissertation is a survey on existing work on the PI graph class and presents new necessary andj or sufficient conditions for a graph to be PI / Mestrado / Teoria da Computação / Mestre em Ciência da Computação

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

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

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-22T06:14:00Z (GMT). No. of bitstreams: 1 Goncalves_AlexandreCasassola_M.pdf: 692699 bytes, checksum: 1b9c1637640944dd47077382ccdbf867 (MD5) Previous issue date: 1997 / Resumo: Não informado. / Abstract: Not informed. / Mestrado / Mestre em Matemática

Orientador: Claudio L. Lucchesi / Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-07-22T14:37:46Z (GMT). No. of bitstreams: 1 Carvalho_MarceloH_D.pdf: 3472839 bytes, checksum: 604447ee0052ba3daa1a6900cea3c290 (MD5) Previous issue date: 1997 / Resumo: O assunto do qual se trata este trabalho se insere na área de teoria dos grafos, e mais especificamente de grafos matching covered, que são grafos conexos em que toda aresta pertence a um emparelhamento perfeito. L. Lovász desenvolveu toda a base da teoria dos grafos matching covered e, como conseqüência, obteve uma caracterização para o matching lattice. Desta caracterização foi possível obter uma prova para uma relaxação da conjectura de Tutte que generaliza o problema das quatro cores. Existem dois procedimentos de decomposição de grafos matching covered que são fundamentais: um deles é a decomposição em cortes justos e o outro é a decomposição em orelhas. Para uma decomposição em orelhas podem ser usadas orelhas simples ou duplas. Uma importante questão é determinar o número mínimo de orelhas duplas de uma decomposição em orelhas de um grafo matching covered. Neste trabalho apresentamos uma resposta para esta questão. Apresentamos também duas conseqüências desta solução: uma delas é que existe uma base para o matching lattice formada apenas por emparelhamentos perfeitos, e a outra é uma caracterização para o Lin(M, Z2 ). Esta última nos permite obter uma prova para outra relaxação da conjectura de Tutte. / Abstract: Matching covered graphs are connected graphs in which every edge lies in a perfect matching. The base of this theory was developed by L. Lovász, and as consequence, a characterization to the matching lattice was obtained. Then it was possible to obtain a proof for a relaxation of a conjecture of Tutte, which is related to the four colors problem. There are two main 'decomposition procedures of a matching covered graph: tight cuts decomposition and ear decomposition. For ear decomposition one can use single or double ears. One important question asks about the minimum number of double ears of any ear decomposition of such graphs. This work gives an answer to this question It is also presented two consequences: that there is a base for the matching lattice formed solely by incidence vectors of perfect matching, and a characterization to Lin (M, Z2 ) which gives a proof to an other relaxation of the Tutte conjecture. / Doutorado / Doutor em Ciência da Computação

Made available in DSpace on 2019-03-30T00:02:07Z (GMT). No. of bitstreams: 0 Previous issue date: 2018-08-30 / Scientific data is being generated and acquired in high volumes in support of studies in many domain areas. In current scenarios, data files containing values of variables (scientific measurements and/or study objects), are ultimately leveraged by data scientists in a series of data preparation tasks that aim to identify relationships between variables in a way that they can be reorganized in an aligned manner, e.g., rewritten as a single line in a tabular file following an alignment criterion. This criterion plays the role of a relationship between a number of distinct variables that is not trivial or easy to elicit looking directly into data files. To address this challenge, we propose a workflow for scientific data characterization and variable alignment based on user-defined indicators. The workflow is able to semantically characterize tabular scientific data files using scientific and domain knowledge in knowledge graphs, allowing data to be queried and retrieved by an ontology-driven faceted-search. A representation of indicators that mimics data users' comparisons and visualizations needs is then leveraged by tasks that are able to produce aligned datasets that can be used directly in routine data tools like R or business intelligence (BI) software for easy graphical plotting. We demonstrate the execution of the workflow in the context of two use cases using data files from the city of Fortaleza, Brazil, where an implementation of this work was used by identified stakeholders. During rounds of evaluation, our approach was verified to ease the process of extracting insights and visualization from scientific data files. To conclude, we discuss the outcomes of this work and their impact on the existing literature, showing ongoing work and potential research directions. Keywords Knowledge graphs; scientific data; data analysis; variable alignment; indicators / Dados científicos são gerados e adquiridos em grandes volumes em apoio a estudos em diversas áreas do conhecimento. Processos de preparação de dados comumente usados fazem uso desses arquivos de dados científicos com a finalidade de identificar relacionamentos implícitos entre variáveis de tal forma que eles possam ser reorganizados de forma alinhada, i.e., reescritos como uma única linha em um arquivo tabular seguindo um critério de alinhamento. Esse critério tem o papel de um relacionamento entre variáveis diversas que não é trivial ou fácil de se extrair verificando diretamente nos arquivos de dados. Para enfrentar esse desafio, propomos um fluxo de trabalho para a caracterização de dados científicos e alinhamento de variáveis baseado na definição de indicadores por usuários dos dados. O fluxo de trabalho tem a capacidade de caracterizar semanticamente arquivos tabulares contendo dados científicos utilizando conhecimento científico e de domínio presente em grafos de conhecimento, permitindo que os dados sejam consultados e recuperados através de uma busca facetada guiada por ontologias. Uma representação de indicadores que reproduz as necessidades de comparações e visualizações de variáveis de usuários dos dados é utilizada para se produzir conjunto de dados alinhados que podem ser utilizados diretamente em ferramentas de dados existentes, como R ou soluções de business intelligence (BI) para plotagem gráfica de modo fácil. Nós demonstramos a execução do fluxo de trabalho no contexto de dois casos de uso utilizando arquivos de dados da cidade de Fortaleza, Brasil, onde uma implementação desse trabalho foi utilizada por partes interessadas. Durante rodadas de avaliação, nossa proposta foi verificada como facilitadora do processo de extração de visões gerais, percepções e visualizações a partir de arquivos de dados científicos. Em conclusão, nós discutimos os resultados desse trabalho e seu impacto na literatura existente, mostrando trabalhos em andamento e potenciais direções de pesquisa. Palavras-chave Grafos de conhecimento; dados científios; análise de dados; alinhamento de variáveis; indicadores

Submitted by LIVIA FREITAS (livia.freitas@ufba.br) on 2013-10-08T15:47:13Z No. of bitstreams: 1 Hugo_Braga-Dissertacao_Mestrado-PPGM.pdf: 1341699 bytes, checksum: dd5c4a50e2339c29a293547d6f02c9de (MD5) / Approved for entry into archive by LIVIA FREITAS(livia.freitas@ufba.br) on 2013-10-08T15:47:22Z (GMT) No. of bitstreams: 1 Hugo_Braga-Dissertacao_Mestrado-PPGM.pdf: 1341699 bytes, checksum: dd5c4a50e2339c29a293547d6f02c9de (MD5) / Made available in DSpace on 2013-10-08T15:47:22Z (GMT). No. of bitstreams: 1 Hugo_Braga-Dissertacao_Mestrado-PPGM.pdf: 1341699 bytes, checksum: dd5c4a50e2339c29a293547d6f02c9de (MD5) / Arvores Steiner são comumente utilizadas para modelar restrições na execução da operação de multicast. Nesta dissertação nós tratamos um novo problema denominado árvore Steiner com Grau Mínimo e fator de dilatação k em Grafos Direcionados (cujo acrônimo em inglês é DSMDStP). Este problema consiste em: dado um grafo direcionado G(V,E), um n´o origem s ∈ V , um fator de dilatação k (k ∈ R+, k ≥ 1) e um conjunto de terminais T ⊆ V \ {s}, encontrar uma arborescência onde o custo entre o nó de origem s em G e cada t ∈ T é menor ou igual a k vezes o custo da menor distância entre este par de nós, ao passo que o grau máximo de saída é minimizado. DSMDStP não admite aproximação sublogarítmica (a menos que NP ⊂ DTIME(nlog log n). Nós descrevemos um algoritmo de aproximação que gera uma arborescência com grau máximo de saída limitado por 2q|T| + 2 + O(log |T|) · d∗, onde d∗ consiste no grau máximo da solução ótima e a arborescência é uma spanner com fator de dilatação (a partir da raiz) de k ·1 + maxt2T {dist(s,t,G)}mint2T dist(s,t,G)}, onde dist(s, t,G) representa o caminho de menor custo entre s e t em G. Embora nosso fator de dilata¸c˜ao viole k, nos experimentos, a restrição de spanner foi satisfeita ou, em média, quase satisfeita. Além disso, o grau de saída medido nos experimentos foi baixo. Nós também descrevemos uma heurística que garante um fator de dilatação de k · (⌊q|T|⌋ + 2), mas não limita o grau máximo de saída. Nos experimentos, a heurística mostrou-se extensível com relação ao grau máximo, além de sempre superar os outros algoritmos nesta métrica. A heurística gerou, adicionalmente, uma spanner com fator de violaçãao baixo. / Salvador