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

Submitted by Marco Antônio de Ramos Chagas (mchagas@ufv.br) on 2018-06-05T13:32:44Z No. of bitstreams: 1 texto completo.pdf: 3038671 bytes, checksum: 989b48613d3d2c169a2fc7e19dc661aa (MD5) / Made available in DSpace on 2018-06-05T13:32:44Z (GMT). No. of bitstreams: 1 texto completo.pdf: 3038671 bytes, checksum: 989b48613d3d2c169a2fc7e19dc661aa (MD5) Previous issue date: 2018-02-28 / Pesquisa desenvolvida a partir das noções sobre grafos, grafos eulerianos, árvores, emparelhamentos em grafos, grafos planares e coloração. Foram abordados alguns dos principais teoremas e lemas, bem como imagens e exemplos para facilitar a leitura. Conclusão da pesquisa com o relato das aulas práticas sobre grafos. / The research was developed based on the notion about graphs, eulerian graphs, trees, matchings in graphs, planar graphs and coloring. Some of the main theorems and lemmas were discussed, as well as images and examples to facilitate reading. The conclusion of the research with the report of the practical classes about graphs. / Sem lattes e agência de fomento.

Orientador: Célia Picinin de Mello / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-27T04:52:30Z (GMT). No. of bitstreams: 1 Vilas-Boas_AloisiodeMenezes_M.pdf: 3075345 bytes, checksum: 59f85d259c9a55bce9d3409c06dd71fa (MD5) Previous issue date: 2015 / Resumo: Seja G um grafo simples. Uma coloração de arestas semiforte de G é uma coloração de arestas de G onde para cada par de vértices adjacentes u,v de G, o conjunto das cores atribuídas às arestas de u é diferente do conjunto das cores atribuídas às arestas de v. O índice cromático semiforte de G, denotado por chi'a(G), é o menor número de cores necessário para construir uma coloração de arestas semiforte para G. Esta coloração foi proposta por Zhang et al. em 2002. Nesse mesmo artigo, os autores conjecturaram que todo grafo simples conexo G, G diferente de C_5, com pelo menos três vértices possui chi'a(G) menor ou igual a Delta(G)+2. Esta conjectura conhecida como conjectura da coloração de arestas semiforte está aberta para grafos arbitrários, mas é válida para algumas classes de grafos. Nesta dissertação, apresentamos alguns resultados sobre a coloração de arestas semiforte. Em seguida, focamos em grafos split. Provamos a conjectura da coloração de arestas semiforte para algumas famílias destes grafos, dentre elas, os split-completos e os split-indiferença. Além disso, determinamos o índice cromático semiforte dos grafos split-indiferença com vértice universal. Para grafos split-indiferença sem vértice universal, exibimos condições para que seu índice cromático semiforte seja igual a Delta(G)+1 e conjecturamos chi'a(G) = Delta(G)+2 caso contrário / Abstract: Let G be a simple graph. An adjacent strong edge-coloring of G is an edge-coloring of G such that for each pair of adjacent vertices u,v of G, the set of colors assigned to the edges incident with u differs from the set of colors assigned to the edges incident with v. The adjacent strong chromatic index, denoted chi'a(G), of G is the minimum number of colors required to produce an adjacent strong edge-coloring for G. This coloring was proposed by Z. Zhang et al. In the same article, the authors conjectured that every simple connected graph G with at least three vertices and G not equal to C_5 (a 5-cycle) has chi'a(G) less or equal then Delta(G)+2. This conjecture is open for arbitrary graphs, but it holds for some classes of graphs. In this dissertation, we present some results on adjacent strong edge-coloring. Then, we focus on split graphs. We prove the conjecture for some families of split graphs including split-complete graphs and split-indifference graphs. Moreover, we determine a necessary condition for split-complete graphs G to have chi'a(G) = Delta(G)+1 and we determine the adjacent strong chromatic index for split-indifference graphs with a universal vertex. For a split-indifference graph G without universal vertices, we give conditions for its adjacent strong chromatic index to be Delta(G)+1 and we conjecture that chi'a(G) = Delta(G)+2, otherwise / Mestrado / Ciência da Computação / Mestre em Ciência da Computação

Magíster en Ciencias de la Ingeniería, Mención Matemáticas Aplicadas. Ingeniero Civil Matemático / Un conjunto de vértices de un grafo se dice convexo si contiene a los vértices de todos los caminos mínimos entre sus vértices. El problema de determinar si un grafo tiene una partición en p conjuntos convexos es NP-completo, pero hay diversas familias de grafos en las que se puede resolver en tiempo polinomial. El foco principal de este trabajo es estudiar el problema de la p-partición convexa en una familia de grafos definida recursivamente al reemplazar los vértices de un bosque por grafos de ésta. Esta familia resulta ser cerrada para subgrafos inducidos. Sin embargo, no queda totalmente determinada la familia de subgrafos prohibidos que determina a esta familia. Además, estos grafos resultan ser perfectos, por lo que varios problemas combinatoriales resultan tener soluciones polinomiales en esta familia. Además, se entrega un algoritmo polinomial para reconocer si un grafo pertenece a esta familia. Para atacar el problema de las particiones convexas en este contexto, combinaremos, mediante programación dinámica, particiones en subgrafos tales que sus particiones convexas son de tres tipos: todos los vértices, particiones en cliques y particiones en cliques más un conjunto localmente convexo. En el caso de las particiones en cliques, se entrega un algoritmo polinomial que lo resuelve. / Este trabajo ha sido parcialmente financiado por CONICYT mediante Proyecto Basal PFB 03

Doctor en Sistemas de Ingeniería / Muchos problemas de decisión industriales o logísticos pueden ser vistos como problemas de optimización y para muchos de ellos no es razonable ocupar datos deterministas. Como veremos en este trabajo en el contexto de despachos de emergencia o de planificación de seguridad, las condiciones reales son desconocidas y tomar decisiones sin considerar esta incertidumbre pueden llevar a resultados catastróficos. La teoría y la aplicación de optimización bajo incertidumbre es un tema que ha generado un amplio área de investigación. Sin embargo, aún existen grandes diferencias en complejidad entre optimización determinista y su versión incierta. En esta tesis, se estudian varios problemas de optimización con aversión al riesgo con un enfasis particular en el problema de camino más corto (RASP), problemas estocásticos en redes en general y juegos de seguridad de Stackelberg. Para obtener distribuciones de tiempos de viaje precisos sobre una red vial a partir de datos GPS del sistema de tránsito, se presenta una revisión de los métodos existentes para proyectar trayectorias GPS y se definen dos nuevos algoritmos: Uno que permite la proyección de datos óptima con respecto a una medida de error convenientemente definida (MOE), y un método heurístico rápido que permite proyectar grandes cantidades de datos de manera contínua (MMH). Se presentan resultados computacionales en redes reales y generadas de gran tamaño. Luego, se desarrollan algoritmos eficientes para problemas de ruteo con aversión al riesgo utilizando métodos de Sample Average Approximation, técnicas de linealización y métodos de descomposición. Se estudian la medida de riesgo entrópica y el Conditional Value at Risk considerando correlaciones entre las variables aleatorias. Se presentan resultados computacionales prometedores en instancias generadas de tamaño mediano. Sin embargo, la naturaleza combinatorial de los problemas los vuelve rapidamente intratable a medida que el tamaño del problema crece. Para hacer frente a esta dificultad computacional, se presentan nuevas formulaciones para problemas en redes difíciles, que tienen un menor número de variables enteras. Estas formulaciones ayudan a derivar esquemas de brancheo que se aprovechan de la estructura especial de las formulaciones propuestas. Se muestra como aplicar estas ideas a los conjuntos de camino simple y de circuito hamiltoniano en redes generales, así como los conjuntos de camino simple y de corte en grafos dirigidos acíclicos (DAG). Este trabajo preliminar muestra ideas prometedoras para resolver problemas difíciles. Finalmente, se exploran las implicaciones de los métodos algortmicos y las formulaciones desarrolladas para resolver RASP en un área diferente. Se presentan nuevas formulaciones y enfoques de resolución para juegos de seguridad de Stackelberg cuando el defensor es averso al riesgo con respecto a la estrategia del atacante. Esto se puede resolver de manera polinomial cuando se enfrenta a un adversario y resolviendo un problema de optimización convexa en números enteros cuando el defensor enfrenta varios tipos de adversarios.

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

Made available in DSpace on 2014-06-12T17:39:48Z (GMT). No. of bitstreams: 1 license.txt: 1748 bytes, checksum: 8a4605be74aa9ea9d79846c1fba20a33 (MD5) Previous issue date: 2006 / Nesta dissertação empregamos a teoria de dinâmica simbólica como ferramenta matemática para abordar o problema da representação de seqüências de símbolos que podem ser modeladas por sistemas dinâmicos simbólicos de memória finita. Utilizando teoria de autômatos, apresentamos novos algoritmos para gerar grafos determinísticos com número mínimo de vértices que apresentam a linguagem de um sistema dinâmico simbólico de memória finita. Para isto, definimos um novo método empregando fundamentos da teoria algébrica de linguagem pata determinar as classes da relação de equivalência ? de Myhill-Nerode sobre a linguagem do sistema dinâmico simbólico de memória finita. O método apresentado é estendido é estendido para sistemas dinâmicos simbólicos de memória finita periódicos que formam a classe (na teoria de dinâmica simbólica) utilizada para modelar conjuntos de seqüências com restrição empregadas tanto para correção de erros quanto para codificação de linha

No description available.

Estágio realizado na ParadigmaXis e orientado pelo Eng.º Filipe Correia / Tese de mestrado integrado. Engenharia Informátca e Computação. Faculdade de Engenharia. Universidade do Porto. 2008