A graph is said to be 2-edge-connected if it remains connected after the deletion of any single edge. Given an unweighted bridgeless graph G with n vertices, the minimum size 2-edge-connected spanning subgraph problem (2EC) is that of finding a 2-edge-connected spanning subgraph of G with the minimum number of edges. This problem has important applications in the design of survivable networks. However, because the problem is NP-hard, it is unlikely that efficient methods exist for solving it. Thus efficient methods that find solutions that are provably close to optimal are sought. In this thesis, an approximation algorithm is presented for 2EC on bridgeless cubic graphs which guarantees to be within 5/4 of the optimal solution value, improving on the previous best proven approximation guarantee of 5/4+ε for this problem. We also focus on the linear programming (LP) relaxation of 2EC, which provides important lower bounds for 2EC in useful solution techniques like branch and bound. The “goodness” of this lower bound is measured by the integrality gap of the LP relaxation for 2EC, denoted by α2EC. Through a computational study, we find the exact value of α2EC for graphs with small n. Moreover, a significant improvement is found for the lower bound on the value of α2EC for bridgeless subcubic graphs, which improves the known best lower bound on α2EC from 9/8 to 8/7.

This thesis investigates the central issues underlying graph analysis, namely, scalability and quality. We first study the incremental problems for graph queries, which aim to compute the changes to the old query answer, in response to the updates to the input graph. The incremental problem is called bounded if its cost is decided by the sizes of the query and the changes only. No matter how desirable, however, our first results are negative: for common graph queries such as graph traversal, connectivity, keyword search and pattern matching, their incremental problems are unbounded. In light of the negative results, we propose two new characterizations for the effectiveness of incremental computation, and show that the incremental computations above can still be effectively conducted, by either reducing the computations on big graphs to small data, or incrementalizing batch algorithms by minimizing unnecessary recomputation. We next study the problems with regards to improving the quality of the graphs. To uniquely identify entities represented by vertices in a graph, we propose a class of keys that are recursively defined in terms of graph patterns, and are interpreted with subgraph isomorphism. As an application, we study the entity matching problem, which is to find all pairs of entities in a graph that are identified by a given set of keys. Although the problem is proved to be intractable, and cannot be parallelized in logarithmic rounds, we provide two parallel scalable algorithms for it. In addition, to catch numeric inconsistencies in real-life graphs, we extend graph functional dependencies with linear arithmetic expressions and comparison predicates, referred to as NGDs. Indeed, NGDs strike a balance between expressivity and complexity, since if we allow non-linear arithmetic expressions, even of degree at most 2, the satisfiability and implication problems become undecidable. A localizable incremental algorithm is developed to detect errors using NGDs, where the cost is determined by small neighbors of nodes in the updates instead of the entire graph. Finally, a rule-based method to clean graphs is proposed. We extend graph entity dependencies (GEDs) as data quality rules. Given a graph, a set of GEDs and a block of ground truth, we fix violations of GEDs in the graph by combining data repairing and object identification. The method finds certain fixes to errors detected by GEDs, i.e., as long as the GEDs and the ground truth are correct, the fixes are assured correct as their logical consequences. Several fundamental results underlying the method are established, and an algorithm is developed to implement the method. We also parallelize the method and guarantee to reduce its running time with the increase of processors.

A graph is said to be 2-edge-connected if it remains connected after the deletion of any single edge. Given an unweighted bridgeless graph G with n vertices, the minimum size 2-edge-connected spanning subgraph problem (2EC) is that of finding a 2-edge-connected spanning subgraph of G with the minimum number of edges. This problem has important applications in the design of survivable networks. However, because the problem is NP-hard, it is unlikely that efficient methods exist for solving it. Thus efficient methods that find solutions that are provably close to optimal are sought. In this thesis, an approximation algorithm is presented for 2EC on bridgeless cubic graphs which guarantees to be within 5/4 of the optimal solution value, improving on the previous best proven approximation guarantee of 5/4+ε for this problem. We also focus on the linear programming (LP) relaxation of 2EC, which provides important lower bounds for 2EC in useful solution techniques like branch and bound. The “goodness” of this lower bound is measured by the integrality gap of the LP relaxation for 2EC, denoted by α2EC. Through a computational study, we find the exact value of α2EC for graphs with small n. Moreover, a significant improvement is found for the lower bound on the value of α2EC for bridgeless subcubic graphs, which improves the known best lower bound on α2EC from 9/8 to 8/7.

La métabolomique est une approche de phénotypage présentant des perspectives prometteuses pour le diagnostic et le suivi de plusieurs pathologies. La technique d'observation la plus utilisée en métabolomique est la spectrométrie de masse (MS). Des développements technologiques récents ont considérablement accru la taille et la complexité des données. Cette thèse s'est concentrée sur deux verrous du traitement de ces données, l'extraction de pics des données brutes et l'annotation des spectres. La première partie de la thèse a porté sur le développement d'un nouvel algorithme de détection de pics pour des données d'analyse par injection en flot continue (Flow Injection Analysis ou FIA), une technique haut-débit. Un modèle dérivé de la physique de l'instrument de mesure prenant en compte la saturation de l'appareil a été proposé. Ce modèle inclut notamment un pic commun à tous les métabolites et un phénomène de saturation spécifique pour chaque ion. Ce modèle a permis de créer une workow qui estime ce pic commun sur des signaux peu bruités, puis l'utilise dans un filtre adapté sur tous les signaux. Son efficacité sur des données réelles a été étudiée et il a été montré que proFIA était supérieur aux algorithmes existants, avait une bonne reproductibilité et était très proche des mesures manuelles effectuées par un expert sur plusieurs types d'appareils. La seconde partie de cette thèse a porté sur le développement d'un outil de détection des similarités structurales d'un ensemble de spectre de fragmentation. Pour ce faire une nouvelle représentation sous forme de graphe a été proposée qui ne nécessite pas de connaître la composition atomique du métabolite. Ces graphes sont de plus une représentation naturelle des spectres MS/MS. Certaines propriétés de ces graphes ont ensuite permis de créer un algorithme efficace de détection des sous graphes fréquents (FSM) basé sur la génération d'arbres couvrants de graphes. Cet outil a été testé sur deux jeux de données différents et a prouvé sa vitesse et son interprétabilité comparé aux algorithmes de l'état de l'art. Ces deux algorithmes ont été implémentés dans des package R, proFIA et mineMS2 disponibles à la communauté. / Metabolomics is a phenotyping approach with promising prospects for the diagnosis and monitoring of several diseases. The most widely used observation technique in metabolomics is mass spectrometry (MS). Recent technological developments have significantly increased the size and complexity of data. This thesis focused on two bottlenecks in the processing of these data, the extraction of peaks from raw data and the annotation of MS/MS spectra. The first part of the thesis focused on the development of a new peak detection algorithm for Flow Injection Analysis (FIA) data, a high-throughput metabolomics technique. A model derived from the physics of the mass spectrometer taking into account the saturation of the instrument has been proposed. This model includes a peak common to all metabolites and a specific saturation phenomenon for each ion. This model has made it possible to create a workflow that estimates the common peak on well-behaved signals, then uses it to perform matched filtration on all signals. Its effectiveness on real data has been studied and it has been shown that proFIA is superior to existing algorithms, has good reproducibility and is very close to manual measurements made by an expert on several types of devices. The second part of this thesis focused on the development of a tool for detecting the structural similarities of a set of fragmentation spectra. To do this, a new graphical representation has been proposed, which does not require the metabolite formula. The graphs are also a natural representation of MS/MS spectra. Some properties of these graphs have then made it possible to create an efficient algorithm for detecting frequent subgraphs (FSM) based on the generation of trees covering graphs. This tool has been tested on two different data sets and has proven its speed and interpretability compared to state-of-the-art algorithms. These two algorithms have been implemented in R, proFIA and mineMS2 packages available to the community.

No description available.

Planar graphs have a rich history that dates back to the 18th Century. They form one of the core concepts of graph theory. In computational graph theory, they offer broad advantages to algorithm design and many groundbreaking results are based on them. Formally, a given graph is either planar or non-planar. However, there exists a diverse set of established measures to estimate how far away from being planar any given graph is. In this thesis, we aim at evaluating and improving algorithms to compute these measures of non-planarity. Particularly, we study (1) the problem of finding a maximum planar subgraph, i.e., a planar subgraph with the least number of edges removed; (2) the problem of embedding a graph on a lowest possible genus surface; and finally (3) the problem of drawing a graph such that there are as few edge crossings as possible. These problems constitute classical questions studied in graph drawing and each of them is NP-hard. Still, exact (exponential time) algorithms for them are of high interest and have been subject to study for decades. We propose novel mathematical programming models, based on different planarity criteria, to compute maximum planar subgraphs and low-genus embeddings. The key aspect of our most successful new models is that they carefully describe also the relation between embedded (sub-)graphs and their duals. Based on these models, we design algorithms that beat the respective state-of-the-art by orders of magnitude. We back these claims by extensive computational studies and rigorously show the theoretical advantages of our new models. Besides exact algorithms, we consider heuristic and approximate approaches to the maximum planar subgraph problem. Furthermore, in the realm of crossing numbers, we present an automated proof extraction to easily verify the crossing number of any given graph; a new hardness result for a subproblem that arises, e.g., when enumerating simple drawings; and resolve a conjecture regarding high node degree in minimal obstructions for low crossing number.

We have two main results. Our first main result is a sharp bound for the number of vertices in a minimal forbidden subgraph for the graphs having minimum rank at most 3 over the finite field of order 2. We also list all 62 such minimal forbidden subgraphs and show that many of these are minimal forbidden subgraphs for any field. Our second main result is a structural characterization of all graphs having minimum rank at most k for any k over any finite field. This characterization leads to a very strong connection to projective geometry and we apply projective geometry results to the minimum rank problem.

No description available.

No description available.

<p>Denote by $k_t(G)$ the number of cliques of order $t$ in a graph $G$ having $n$ vertices. Let $k_t(n) = \min\{k_t(G)+k_t(\overline{G}) \}$ where $\overline{G}$ denotes the complement of $G$. Let $c_t(n) = {k_t(n)}/{\tbinom{n}{t}}$ and $c_t$ be the limit of $c_t(n)$ for $n$ going to infinity. A 1962 conjecture of Erd\H{o}s stating that $c_t = 2^{1-\tbinom{t}{2}}$ was disproved by Thomason in 1989 for all $t\geq 4$. Tighter counterexamples have been constructed by Jagger, {\v S}{\v t}ov{\' \i}{\v c}ek and Thomason in 1996, by Thomason for $t\leq 6$ in 1997, and by Franek for $t=6$ in 2002. Further tightenings $t=6,7$ and $8$ was recently obtained by Deza, Franek, and Liu.</p> <p>We investigate the computational framework used by Deza, Franek, and Liu. In particular, we present the benefits and limitations of different parallel computer memory architectures and parallel programming models. We propose a functional decomposition approach which is implemented in C++ with POSIX thread (Pthread) libraries for multi-threading. Computational benchmarking on the parallelized framework and a performance analysis including a comparison with the original computational framework are presented.</p> / Master of Science (MSc)