A graph is k-resilient if it is possible to construct local routing tables for each vertex such that we can reach a specified destination vertex from anywhere in the graph. There is a conjecture that k-resilience is equivalent to (k+1)-connectivity. We prove this for 3-edge-connected graphs and 4-edge-connected planar triangulations. In the proof we use independent directed spanning trees. Two spanning trees are independent if they share no common edge with the same direction. For k=3,4 we show that a graph has k independent spanning trees if and only if it is k-edge-connected. We search for the spanning trees constructively through reductions of parts of the graph. Some of these reductions can also be used in a general k- connected case. Powered by TCPDF (www.tcpdf.org)

The main focus of this thesis are hypercubes. In the first part, we introduce hypercubes, which form an interesting class of graphs that has practical uses in networks and distributed computing. Because of their varied applications, the thesis describes the graph-theory problems related to hypercubes such as searching for detour spanners, minimizing their maximal degree and finding multiple edge- disjoint spanners. It also overviews current results on selected hypercube problems and proposes a solution using a genetic algorithm. The genetic algorithm is designed, implemented and its performance is evaluated. The conclusion is that applying a genetic algorithm to some hypercube problems is a viable, but not the most effective method.

Graphlet enumeration is a basic task in graph analysis with many applications. Thus it is important to be able to perform this task within a reasonable amount of time. However, this objective is challenging when the input graph is very large, with millions of nodes and edges. Known solutions are limited in terms of scalability. Distributed computing is often proposed as a solution to improve scalability. How- ever, it has to be done carefully to reduce the overhead cost and to really benefit from the distributed solution. We study the enumeration of four-node graphlets in undirected graphs using a distributed platform. We propose an efficient distributed solution which significantly surpasses the existing solutions. With this method we are able to process larger graphs that have never been processed before and enumerate quadrillions of graphlets using a modest cluster of machines. We convincingly show the scalability of our solution through experimental results. / Graduate

A graph is a data structure that contains a set of nodes and a set of edges connecting these nodes. Nodes represent objects while edges model relationships among these objects. Graphs are used in various domains due to their ability to model complex relations among several objects. Given an input graph, the Frequent Subgraph Mining (FSM) task finds all subgraphs with frequencies exceeding a given threshold. FSM is crucial for graph analysis, and it is an essential building block in a variety of applications, such as graph clustering and indexing. FSM is computationally expensive, and its existing solutions are extremely slow. Consequently, these solutions are incapable of mining modern large graphs. This slowness is caused by the underlying approaches of these solutions which require finding and storing an excessive amount of subgraph matches. This dissertation proposes a scalable solution for FSM that avoids the limitations of previous work. This solution is composed of four components. The first component is a single-threaded technique which, for each candidate subgraph, needs to find only a minimal number of matches. The second component is a scalable parallel FSM technique that utilizes a novel two-phase approach. The first phase quickly builds an approximate search space, which is then used by the second phase to optimize and balance the workload of the FSM task. The third component focuses on accelerating frequency evaluation, which is a critical step in FSM. To do so, a machine learning model is employed to predict the type of each graph node, and accordingly, an optimized method is selected to evaluate that node. The fourth component focuses on mining dynamic graphs, such as social networks. To this end, an incremental index is maintained during the dynamic updates. Only this index is processed and updated for the majority of graph updates. Consequently, search space is significantly pruned and efficiency is improved. The empirical evaluation shows that the proposed components significantly outperform existing solutions, scale to a large number of processors and process graphs that previous techniques cannot handle, such as large and dynamic graphs.

This thesis introduces exact (ILP- and SAT/PBS-based) algorithms for the Minimum Genus Problem and the Maximum Planar Subgraph Problem. It also considers general limits of approximation algorithms for the Maximum Planar Subgraph Problem.

<p>The densest subgraph problem is an important problem with both theoretical and practical significance. We consider a variant of the problem, the directed densest subgraph problem, under the partially dynamic setting of edge insertions only. We give a algorithm maintaining a (1-ε)-approximate directed densest subgraph in O(log³n/ε⁶) amortized time per edge insertion, based on earlier work by Chekuri and Quanrud. This result partially improves on an earlier result by Sawlani and Wang, which guarantees O(log⁵n/ε⁷) worst case time for edge insertions and deletions.</p>

No description available.

Convex cycles play a role e.g. in the context of product graphs. We introduce convex cycle bases and describe a polynomial-time algorithm that recognizes whether a given graph has a convex cycle basis and provides an explicit construction in the positive case. Relations between convex cycles bases and other types of cycles bases are discussed. In particular we show that if G has a unique minimal cycle bases, this basis is convex. Furthermore, we characterize a class of graphs with convex cycles bases that includes partial cubes and hence median graphs. (authors' abstract) / Series: Research Report Series / Department of Statistics and Mathematics

Un des principaux défis de la bioinformatique moderne est de saisir le sens des données biologiques en constante croissance. Il est prépondérant de trouver de bons modèles pour toutes ces données, modèles qui servent à la fois à expliquer les données et à produire des réponses aux questions biologiques sous-jacentes. Une des nombreuses difficultés d’une telle approche est la grande variété dans les types des données manipulées. La biologie computationnelle moderne propose des approches qui combinent ces types de données dans des techniques dites intégratives. Cette thèse contribue au problème de l’identification de module biologique en intégrant les informations de conservation dans les modèles modernes d’identification d’ensemble de protéines. Nous introduisons un modèle pour la détection de modules connexes actifs et conservés, c’est-à-dire des modules connexes dont une majorité d’éléments sont similaires entre deux espèces. Nous présentons une formulation de notre modèle sous forme de programmation linéaire en nombres entiers, et proposons un algorithme branch-and-cut qui résout le modèle à l’optimalité en temps raisonnable. Nous appliquons notre modèle sur des données de différentiation cellulaire, à savoir les cellules Th0 en Th17 pour l’humain et la sourie. Nous analysons également notre modèle du point du vue de la complexité algorithmique, et fournissons des résultats pour le cas général ainsi que des cas spéciaux. / One of the major challenge for modern bioinformatics is making sense of the ever increasing size of biological data. Finding good models for all this data, models that can both explain the data and provide insight into biological questions, is paramount. One of the many difficulties of such path is the variety in the types of data. Modern computational biology approaches combine these many data into integrative approaches, that combine the knowledge inside the data in the hope to extract higher level information. This thesis contribute to the biological module identification problem by integrating conservation information with modern models of modular detection of protein sets. We introduce a model for the detection of conserved active connected modules, that is connected modules that are conversed across two species. These active connected modules are similar in sequence composition between the two species. We present a mixed-integer linear programming formulation of our model, and propose a branch-and-cut algorithm to solve to provable optimality in reasonable run time. We apply our model to cell line differentiation data, namely Th0 into Th17 for both human and mouse. We also analyse the model from a complexity standpoint, and provide general as well as special cases complexity results.

No description available.