Automated analysis of networks of interactions between proteins has become pervasive in molecular biology. Each node in such a network represents a protein and each edge an interaction between two proteins. Nearly every publication that uses network analysis includes a visualization of a graph in which the nodes and edges are laid out in two dimensions. Several systems implement multiple types of graph layout algorithms and make them easily accessible to scientists. Despite the existence of these systems, interdisciplinary research teams in computational biology face several challenges in sharing computed networks and interpreting them. This thesis presents two systemsGraphSpace and GraphCrowdthat together enhance network-based collaboration. GraphSpace users can automatically and rapidly share richly- annotated networks, irrespective of the algorithms or software used to generate them. A user may search for networks that contain a specific node or edge, or a collection of nodes and edges. Users can manually modify a layout, save it, and share it with other users. Users can create private groups, invite other users to join groups, and share networks with group members. Upon publication, researchers may make networks public and provide a URL in the paper. GraphCrowd addresses the challenging posed by automated layout algorithms, which incorporate almost no knowledge of the biological information underlying the networks. These algorithms compel researchers to use their knowledge and intuition to modify the node and edge positions manually to bring out salient features. GraphCrowd focuses on signaling networks, which connect proteins that represent a cells response to external signals. Treating network layout as a design problem, GraphCrowd explores the feasibility of leveraging human computation via crowdsourcing to create simplified and meaningful visualizations. GraphCrowd provides a streamlined interface that enables crowd workers to easily manipulate networks to create layouts that follow a specific set of guidelines. GraphCrowd also implements an interface to allow a user (e.g., an expert or a crowd worker) to evaluate how well a layout conforms to the guidelines. We use GraphCrowd to address two research questions: (i) Can we harness the power of crowdsourcing to create simplified, biologically meaningful visualizations of signaling networks?(ii) Can crowd workers rate layouts similarly to how an expert with domain knowledge would rate them? We design two systematic experiments that enable us to answer both questions in the affirmative. This thesis establishes crowdsourcing as a powerful methodology for laying out complex signaling networks. Moreover, by developing appropriate domain-specific guidelines for crowd workers, GraphCrowd can be generalized to a variety of applications. / Master of Science

Graphs are a commonly used abstraction for diverse kinds of interactions, e.g., on Twitter and Facebook. Different kinds of topological properties of such graphs are computed for gaining insights into their structure. Computing properties of large real networks is computationally very challenging. Further, most real world networks are dynamic, i.e., they change over time. Therefore there is a need for efficient dynamic algorithms that offer good space-time trade-offs. In this thesis we study the problem of computing the reachability set size of a vertex, which is a fundamental problem, with applications in databases and social networks. We develop the first Giraph based algorithms for different dynamic versions of these problems, which scale to graphs with millions of edges. / Master of Science

Given a graph, a matching is a set of vertex-disjoint edges. Graph matchings have been well studied, since they play a fundamental role in algorithmic theory as well as motivate many practical applications. Of particular interest is the problem of finding a maximum cardinality matching of a graph. Also of interest is the weighted variant: the problem of computing a minimum-cost maximum cardinality matching. For an arbitrary graph with m edges and n vertices, there are known, long-standing combinatorial algorithms that compute a maximum cardinality matching in O(m\sqrt{n}) time. For graphs with non-negative integer edge costs at most C, it is known how to compute a minimum-cost maximum cardinality matching in roughly O(m\sqrt{n} log(nC)) time using combinatorial methods. While non-combinatorial methods exist, they are generally impractical and not well understood due to their complexity. As a result, there is great interest in obtaining faster matching algorithms that are purely combinatorial in nature. Improving existing combinatorial algorithms for arbitrary graphs is considered to be a very difficult problem. To make the problem more approachable, it is desirable to make some additional assumptions about the graph. For our work, we make two such assumptions. First, we assume the graph is bipartite. Second, we assume that the graph has a small balanced separator, meaning it is possible to split the graph into two roughly equal-size components by removing a relatively small portion of the graph. Several well-studied classes of graphs have separator-like properties, including planar graphs, minor-free graphs, and geometric graphs. For such graphs, we describe a framework, a general set of techniques for designing efficient algorithms. We demonstrate this framework by applying it to yield polynomial-factor improvements for several open-problems in bipartite matching. / Doctor of Philosophy / Assume we are given a list of objects, and a list of compatible pairs of these objects. A matching consists of a chosen subset of these compatible pairs, where each object participates in at most one chosen pair. For any chosen pair of objects, we say the these two objects are matched. Generally, we seek to maximize the number of compatible matches. A maximum cardinality matching is a matching with the largest possible size. In many cases, there are multiple options for maximizing the number of compatible pairings. While maximizing the size of the matching is often the primary concern, one may also seek to minimize the cost of the matching. This is known as the minimum-cost maximum-cardinality matching problem. These two matching problems have been well studied, since they play a fundamental role in algorithmic theory as well as motivate many practical applications. Our interest is in the design of algorithms for both of these problems that are efficiently scalable, even as the number of objects involved grows very large. To aid in the design of scalable algorithms, we observe that some inputs have good separators, meaning that by removing some subset S of objects, one can divide the remaining objects into two sets V and V', where all pairs of objects between V and V' are incompatible. We design several new algorithms that exploit good separators, and prove that these algorithms scale better than previously existing approaches.

We consider the spectrum of the Schrödinger operator on an octagonal lattice using the Floquet-Bloch transform of the Laplacian. We will first consider the spectrum of the Laplacian in detail and prove various properties thereof, including spectral-band limits and locations of singularities. In addition, we will prove that Schrödinger operators with 1-1 periodic potentials can open at most two gaps in the spectrum precisely at energies $pm1$, and that a third gap can open at 0 for 2-2 periodic potentials. We describe in detail the structure of these operators for higher periods, and motivate our expectations of their spectra. / Master of Science / In quantum physics, we would like the capability to model environments, such as magnetic fields, that interact with electrons or other quantum entities. The fields of graph theory and functional analysis within mathematics provide tools which relate well-understood mathematical concepts to these physical interactions. In this work, we use these tools to describe these environments using previously employed techniques in new ways.

No description available.

Muitos dos sistemas de computação existentes atualmente são concorrentes, ou seja, neles constam diversas entidades que, ao mesmo tempo, operam sobre um conjunto de recursos compartilhados. Nesse contexto, devemos controlar a concorrência das diversas operações realizadas, ou então a interferência entre elas poderia causar inconsistências nos recursos compartilhados ou nas próprias operações realizadas. Nesse texto, vamos tratar especificamente de estruturas de dados concorrentes, ou seja, estruturas de dados cujas operações associadas -- consideramos inserção, remoção e busca -- sejam passíveis de execução simultânea por diversas entidades. Tendo em vista o controle da concorrência, vamos adotar uma abordagem baseada no emprego de locks, uma primitiva de sincronização muito usual na literatura. Nossa discussão será apresentada em termos de certas estruturas de dados chamadas skip graphs, que têm propriedades interessantes para outros contextos, como o contexto de sistemas distribuídos. / Many existing computer systems are concurrent, or, in other words, they are composed of many entities that, at the same time, operate over some set of shared resources. In this context, we must control the concurrency of the operations, otherwise the interference between them could cause inconsistencies in the shared resources or in the operations themselves. In this text, we specifically discuss concurrent data structures, or, in other words, data structures over which the associated operations -- we consider insertion, removal and search -- could be executed simultaneously by various entities. In order to control the concurrency, we will employ an aproach based on the use of locks, a widely known synchronization primitive in the literature. Our discussion will be presented in terms of data structures called skip graphs, which have interesting properties in other contexts, as the context of distributed systems.

A caracterização de redes e o estudo de sistemas, ambos utilizando grafos, é algo muito usado por várias áreas científicas. Uma das linhas deste estudo é denominada de grafos aleatórios, que por sua vez auxilia na criação de modelos para análise de redes reais. Consideramos um modelo de grafo aleatório não homogêneo criado por Kang, Pachón e Rodríguez (2016), cuja construção é feita a partir da realização do grafo binomial G(n; p). Para este modelo, estudamos argumentos e métodos usados para encontrar resultados sobre o limiar de conectividade, importante propriedade relacionada a existência assintótica de vértices e componentes isolados. Em seguida, constatamos algumas características positivas e negativas a respeito da utilização do grafo para modelar redes reais complexas, onde usamos de simulações computacionais e medidas topológicas. / The characterization of networks and the study of systems, both using graphs, is very used by several scientific areas. One of the lines of this study is called random graphs, which in turn assists in creating models for the analysis of real networks. We consider an inhomogeneous random graph model created by Kang, Pachón e Rodríguez (2016), where its construction is made from the realization of the binomial graph G(n; p). For this model, we studied the arguments and methods used to find results on the connectivity threshold, important property related to asymptotic existence of vertices and isolated components. Then we found some positive and negative characteristics about the use of the graph to model complex real networks, using computer simulations and topological measures.

Submitted by Rosivalda Pereira (mrs.pereira@ufma.br) on 2017-08-25T20:24:28Z No. of bitstreams: 1 JandersonFreitas.pdf: 2087995 bytes, checksum: e49b1008df3093f81aeb841870a06df9 (MD5) / Made available in DSpace on 2017-08-25T20:24:28Z (GMT). No. of bitstreams: 1 JandersonFreitas.pdf: 2087995 bytes, checksum: e49b1008df3093f81aeb841870a06df9 (MD5) Previous issue date: 2017-05-08 / The paper presents problem solving using Graph Theory and Euler’s Theorem. The research performs specific activities in high school involving graphs in various applications of the Euler relation as a problem solving method with Graph Theory. The relationship of Euler is presented in a Geometric view and by the graphs planning. The research proposes a link between the students ’daily problems with the modeling of problem situations by the Graph Theory, specifically the planar graphs solved with the implementation of Euler’ s Theorem focused on the teaching of basic mathematics. Applications of Graph Theory are shown in solving problems with the bridges of the city of Barra do Corda and the students’ school life. / O trabalho apresenta a resolução de problemas utilizando a Teoria dos Grafos e o Teorema de Euler. Uma pesquisa que executa atividades específicas no ensino médio envolvendo grafos em várias aplicações da relação de Euler como método de resolução de problemas com Teoria dos Grafos. A relação de Euler é apresentada em uma visão Geométrica e pela planificação dos grafos. Propondo um elo entre os problemas do cotidiano dos alunos com a modelagem de situações problema pela Teoria dos Grafos, especificamente os grafos planares resolvidos com a implementação do Teorema de Euler voltado ao ensino de matemática básica. São mostradas aplicações da Teoria dos Grafos na resolução de problemas com as pontes da cidade de Barra do Corda e da vida escolar dos alunos.

Submitted by Jorge Silva (jorgelmsilva@ufrrj.br) on 2017-08-29T17:44:42Z No. of bitstreams: 1 2016 - Victor Leite Alves.pdf: 3650645 bytes, checksum: 38df3227b0440f1bbe6403a506d9a55e (MD5) / Made available in DSpace on 2017-08-29T17:44:42Z (GMT). No. of bitstreams: 1 2016 - Victor Leite Alves.pdf: 3650645 bytes, checksum: 38df3227b0440f1bbe6403a506d9a55e (MD5) Previous issue date: 2016-08-03 / CAPES / The aim of this work is to describe an experience using problems on paths in Graphs with students of the first year of high school from two schools through a case study. There were 48 students from two schools, one located in Resende and another in Quatis, in Rio de Janeiro. The Basic Theory of Graphs initially has simple and intuitive concepts which may be used as powerful tools for solving various kinds of optimization problems. Many of the problems are present in the universe of students, such as the way Google Maps draws the shortest path between the starting point and destination, the procedure that can be used for a GPS to calculate a route, the path that optimizes the work a postman who has to go through several streets (without repetition) and return to the headquarters of the post office, among others. Bring real problems into the classroom is a challenge to the teacher, and solve them with simple techniques in the classroom is an even greater challenge, and this work attempts to perform a little experiment in which this dual task is conducted with some simple techniques from Graphs applied to the students everyday problems. Four basic 50-minute classes are held on Graphs and are taught some of their techniques. But before the classes, two tests are performed: a motivational test (based on Gontijo test) that assesses how students study and enjoy mathematics, and a test involving problems from the universe of the students that could be solved with graphs techniques, but also with what students already know from high school. After the classes, a new motivational test evaluates how much they enjoyed the activities with graphs and a new content test is performed, now being permitted to use the graphs techniques. Finally a survey was made on the results obtained by observing the improvement obtained by the students involved in the process and which had more difficulty, thus completing the experience. / O objetivo deste trabalho ? descrever uma experi?ncia utilizando problemas relacionados a caminhos em Grafos com alunos do primeiro ano do ensino m?dio de duas escolas da rede estadual de ensino atrav?s de um estudo de caso. Foram 48 alunos de duas escolas da rede estadual de ensino, uma situada no munic?pio de Resende e outra no munic?pio de Quatis, no Rio de Janeiro. A Teoria B?sica de Grafos possui inicialmente conceitos simples e intuitivos, mas que podem ser utilizados como poderosas ferramentas para a resolu??o de diversos tipos de problemas de otimiza??o. Muitos dos problemas est?o presentes no universo dos alunos, como a maneira como o Google Maps tra?a o menor caminho entre o ponto de partida e o destino, o procedimento que pode ser usado por um GPS para calcular uma rota, o caminho que otimiza o trabalho de um carteiro que tem que percorrer v?rias ruas (sem repeti??o) e voltar ? sede dos correios, entre outros. Uma vez que trazer problemas reais para dentro da sala de aula ? um desafio ao professor, e resolv?-los com t?cnicas simples na sala de aula ? um desafio ainda maior, o presente trabalho tenta realizar uma pequena experi?ncia em que esta dupla tarefa ? conduzida com algumas t?cnicas simples de Grafos aplicadas a problemas do cotidiano dos alunos. S?o realizadas 4 aulas b?sicas de 50 minutos sobre Grafos e s?o ensinadas algumas de suas t?cnicas. Mas antes das aulas, dois testes s?o realizados: um teste motivacional (baseado no teste de Gontijo) que avalia o quanto os alunos estudam e gostam de Matem?tica, e um teste envolvendo problemas do universo dos alunos que poderiam ser resolvidos com t?cnicas de Grafos, mas tamb?m com o que os alunos j? sabem do ensino m?dio. Ap?s as aulas, um novo teste motivacional avalia o quanto eles gostaram das atividades realizadas com Grafos e um novo teste de conte?do ? realizado, j? sendo permitida a utiliza??o das t?cnicas de Grafos. Finalmente foi feito um levantamento sobre os resultados obtidos, observando a melhora obtida pelos alunos envolvidos durante o processo e onde tiveram mais dificuldade, concluindo assim a experi?ncia.

A model for DNA recombination uses 4-valent rigid vertex graphs, called assembly graphs. An assembly graph, similarly to the projection of knots, can be associated with an unsigned Gauss code, or double occurrence word. We define biologically motivated reductions that act on double occurrence words and, in turn, on their associated assembly graphs. For every double occurrence word w there is a sequence of reduction operations that may be applied to w so that what remains is the empty word, [epsilon]. Then the nesting index of a word w, denoted by NI(w), is defined to to be the least number of reduction operations necessary to reduce w to [epsilon]. The nesting index is the first property of assembly graphs that we study. We use chord diagrams as tools in our study of the nesting index. We observe two double occurrence words that correspond to the same circle graph, but that have arbitrarily large differences in nesting index values. In 2012, Buck et al. considered the cellular embeddings of assembly graphs into orientable surfaces. The genus range of an assembly graph [Gamma], denoted gr([Gamma]), was defined to be the set of integers g where g is the genus of an orientable surface F into which [Gamma] cellularly embeds. The genus range is the second property of assembly graphs that we study. We generalize the notion of the genus range to that of the genus spectrum, where for each g [isin] gr([Gamma]) we consider the number of orientable surfaces F obtained from [Gamma] by a special construction, called a ribbon graph construction, that have genus g. By considering this more general notion we gain a better understanding of the genus range property. Lastly, we show how one can obtain the genus spectrum of a double occurrence word from the genus spectrums of its irreducible parts, i.e., its double occurrence subwords. In the final chapter we consider constructions of double occurrence words that recognize certain values for nesting index and genus range. In general, we find that for arbitrary values of nesting index [ge] 2 and genus range, there is a double occurrence word that recognizes those values.