We consider the graphs induced by the noncommutativity of groups and discuss some properties of the largest complete subgraphs of these graphs.

Genes can be associated in numerous ways, e.g. by co-expression in micro-arrays, co-regulation in operons and regulons or co-localization on the genome. Association of genes often indicates that they contribute to a common biological function, such as a pathway. The aim of this thesis is to predict metabolic pathways from associated enzyme-coding genes. The prediction approach developed in this work consists of two steps: First, the reactions are obtained that are carried out by the enzymes coded by the genes. Second, the gaps between these seed reactions are filled with intermediate compounds and reactions. In order to select these intermediates, metabolic data is needed. This work made use of metabolic data collected from the two major metabolic databases, KEGG and MetaCyc. The metabolic data is represented as a network (or graph) consisting of reaction nodes and compound nodes. Interme- diate compounds and reactions are then predicted by connecting the seed reactions obtained from the query genes in this metabolic network using a graph algorithm. In large metabolic networks, there are numerous ways to connect the seed reactions. The main problem of the graph-based prediction approach is to differentiate biochemically valid connections from others. Metabolic networks contain hub compounds, which are involved in a large number of reactions, such as ATP, NADPH, H2O or CO2. When a graph algorithm traverses the metabolic network via these hub compounds, the resulting metabolic pathway is often biochemically invalid. In the first step of the thesis, an already existing approach to predict pathways from two seeds was improved. In the previous approach, the metabolic network was weighted to penalize hub compounds and an extensive evaluation was performed, which showed that the weighted network yielded higher prediction accuracies than either a raw or filtered network (where hub compounds are removed). In the improved approach, hub compounds are avoided using reaction-specific side/main compound an- notations from KEGG RPAIR. As an evaluation showed, this approach in combination with weights increases prediction accuracy with respect to the weighted, filtered and raw network. In the second step of the thesis, path finding between two seeds was extended to pathway prediction given multiple seeds. Several multiple-seed pathay prediction approaches were evaluated, namely three Steiner tree solving heuristics and a random-walk based algorithm called kWalks. The evaluation showed that a combination of kWalks with a Steiner tree heuristic applied to a weighted graph yielded the highest prediction accuracy. Finally, the best perfoming algorithm was applied to a microarray data set, which measured gene expression in S. cerevisiae cells growing on 21 different compounds as sole nitrogen source. For 20 nitrogen sources, gene groups were obtained that were significantly over-expressed or suppressed with respect to urea as reference nitrogen source. For each of these 40 gene groups, a metabolic pathway was predicted that represents the part of metabolism up- or down-regulated in the presence of the investigated nitrogen source. The graph-based prediction of pathways is not restricted to metabolic networks. It may be applied to any biological network and to any data set yielding groups of associated genes, enzymes or compounds. Thus, multiple-end pathway prediction can serve to interpret various high-throughput data sets.

The direct sum of a finite number of graph classes H_1, ..., H_k is defined as the set of all graphs formed by taking the union of graphs from each of the H_i. The join of these graph classes is similarly defined as the set of all graphs formed by taking the join of graphs from each of the H_i. In this paper we show that if each H_i has a forbidden subgraph characterization then the direct sum and join of these H_i also have forbidden subgraph characterizations. We provide various results which in many cases allow us to exactly determine the minimal forbidden subgraphs for such characterizations. As we develop these results we are led to study the minimal graphs which are universal over a given list of graphs, or those which contain each graph in the list as an induced subgraph. As a direct application of our results we give an alternate proof of a theorem of Barrett and Loewy concerning a forbidden subgraph characterization problem.

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.

This thesis proposes an expressive yet efficient declarative framework for graph matching in constraint programming (CP), and focuses on efficient algorithms to solve the subgraph isomorphism problem. The framework is based on graph and map variables, and specific graph morphism constraints. This allows to model and solve various graph matching problems, avoiding the tedious development of dedicated and specific algorithms. A specialized filtering algorithm is proposed for the subgraph isomorphism problem, which uses the semantic of the problem as well as the global structure of the two input graphs. It is shown that it is the state-of-the-art filtering algorithm, compared to dedicated algorithms and other CP approaches. Various search techniques from CP are also extended to the subgraph isomorphism problem. An automatic detection and exploitation of symmetries for the subgraph isomorphism problem is proposed, together with a decomposition approach of the search. The significance of this thesis lies in the fact that, even though the framework is expressive, CP can be considered as the state-of-the-art for subgraph isomorphism, outperforming the dedicated known algorithms on current benchmarks.

Explanation-based Generalization requires that the learner obtain an explanation of why a precedent exemplifies a concept. It is, therefore, useless if the system fails to find this explanation. However, it is not necessary to give up and resort to purely empirical generalization methods. In fact, the system may already know almost everything it needs to explain the precedent. Learning by Failing to Explain is a method which is able to exploit current knowledge to prune complex precedents, isolating the mysterious parts of the precedent. The idea has two parts: the notion of partially analyzing a precedent to get rid of the parts which are already explainable, and the notion of re-analyzing old rules in terms of new ones, so that more general rules are obtained.

We consider complete subgraphs of the graph induced by the noncommutativity of a ring, and prove that the graph induced by an infinite noncommutative prime ring contains an infinite complete subgraph. We also compute the clique number and the chromatic number of the graphs induced by some concrete graphs.

Simultaneous localization and mapping (SLAM) and Structure from Motion (SfM) are important problems in robotics and computer vision. One of the challenges is to solve a large-scale optimization problem associated with all of the robot poses, camera parameters, landmarks and measurements. Yet neither of the two reigning paradigms, direct and iterative methods, scales well to very large and complex problems. Recently, the subgraph-preconditioned conjugate gradient method has been proposed to combine the advantages of direct and iterative methods. However, how to find a good subgraph is still an open problem. The goal of this dissertation is to address the following two questions: (1) What are good subgraph preconditioners for SLAM and SfM? (2) How to find them? To this end, I introduce support theory and support graph theory to evaluate and design subgraph preconditioners for SLAM and SfM. More specifically, I make the following contributions: First, I develop graphical and probabilistic interpretations of support theory and used them to visualize the quality of subgraph preconditioners. Second, I derive a novel support-theoretic metric for the quality of spanning tree preconditioners and design an MCMC-based algorithm to find high-quality subgraph preconditioners. I further improve the efficiency of finding good subgraph preconditioners by using heuristics and domain knowledge available in the problems. Our results show that the support-theoretic subgraph preconditioners significantly improve the efficiency of solving large SLAM problems. Third, I propose a novel Hessian factor graph representation, and use it to develop a new class of preconditioners, generalized subgraph preconditioners, that combine the advantages of subgraph preconditioners and Hessian-based preconditioners. I apply them to solve large SfM problems and obtain promising results. Fourth, I develop the incremental subgraph-preconditioned conjugate gradient method for large-scale online SLAM problems. The main idea is to combine the advantages of two state-of-the-art methods, incremental smoothing and mapping, and the subgraph-preconditioned conjugate gradient method. I also show that the new method is efficient, optimal and consistent. To sum up, preconditioning can significantly improve the efficiency of solving large-scale SLAM and SfM problems. While existing preconditioning techniques do not utilize the problem structure and have no performance guarantee, I take the first step toward a more general setting and have promising results.

In 2003 at Eurocomb conference J. Barát and C. Thomassen presented definition and basic results in edge partitioning of graphs. Edge partitioning is basically possibility to cover edges of the graph using connected subgraphs of prescribed size. Graph has edge partitioning property if and only if it can be covered for all prescribed subgraphs sizes. Our work is focused on edge partitioning, in which there are less results known, compared to vertex partitioning. We proof, that edge partitioning is implied by existence of open dominating trail and therefore with edge 4-connectivity. We also define limited version of edge partitioning, spectrum of partitioning and we proof some claims that are true for all graphs. We also explore limited partitioning on some specific classes of graphs.