Connectivity is a fundamental tool for matroid theorists, which has become increasingly important in the eventual solution of many problems in matroid theory. Loosely speaking, connectivity can be used to help describe a matroid's structure. In this thesis, we prove a series of results that further the knowledge and understanding in the field of matroid connectivity. These results fall into two parts. First, we focus on 3-connected matroids. A chain theorem is a result that proves the existence of an element, or elements, whose deletion or contraction preserves a predetermined connectivity property. We prove a series of chain theorems for 3-connected matroids where, after fixing a basis B, the elements in B are only eligible for contraction, while the elements not in B are only eligible for deletion. Moreover, we prove a splitter theorem, where a 3-connected minor is also preserved, resolving a conjecture posed by Whittle and Williams in 2013. Second, we consider k-connected matroids, where k >= 3. A certain tree, known as a k-tree, can be used to describe the structure of a k-connected matroid. We present an algorithm for constructing a k-tree for a k-connected matroid M. Provided that the rank of a subset of E(M) can be found in unit time, the algorithm runs in time polynomial in |E(M)|. This generalises Oxley and Semple's (2013) polynomial-time algorithm for constructing a 3-tree for a 3-connected matroid.

The estimation of optical flow has become a vital research field in image sequence analysis especially in past two decades, which found applications in many fields such as stereo optics, video compression, robotics and computer vision. In this thesis, the complex wavelet based algorithm for the estimation of optical flow developed by Magarey and Kingsbury is implemented and investigated. The algorithm is based on a complex version of the discrete wavelet transform (CDWT), which analyzes an image through blocks of filtering with a set of Gabor-like kernels with different scales and orientations. The output is a hierarchy of scaled and subsampled orientation-tuned subimages. The motion estimation algorithm is based on the relationship between translations in image domain and phase shifts in CDWT domain, which is satisfied by the shiftability and interpolability property of CDWT. Optical flow is estimated by using this relationship at each scale, in a coarse-to-fine (hierarchical) manner, where information from finer scales is used to refine the estimates from coarser scales. The performance of the motion estimation algorithm is investigated with various image sequences as input and the effects of the options in the algorithm like curvature-correction, interpolation kernel between levels and some parameter values like confidence threshold iv maximum number of CDWT levels and minimum finest level of detail are also experimented and discussed. The test results show that the method is superior to other well-known algorithms in estimation accuracy, especially under high illuminance variations and additive noise.

Dans cette thèse, nous étudions les décompositions arborescentes qui satisfont certaines contraintes supplémentaires et nous proposons des algorithmes pour les calculer dans certaines classes de graphes. Finalement, nous résolvons des problèmes liés au routage en utilisant ces décompositions ainsi que des propriétés structurelles des graphes. Cette thèse est divisée en deux parties. Dans la première partie, nous étudions les décompositions arborescentes satisfaisant des propriétés spécifiques. Dans le Chapitre 2, nous étudions les décompositions de taille minimum, c’est-À-Dire avec un nombre minimum de sacs. Etant donné une entier k 4 fixé, nous prouvons que le problème de calculer une décomposition arborescente de largeur au plus k et de taille minimum est NP-Complet dans les graphes de largeur arborescente au plus 4. Nous décrivons ensuite des algorithmes qui calculent des décompositions de taille minimum dans certaines classes de graphes de largeur arborescente au plus 3. Ces résultats ont été présentés au workshop international ICGT 2014. Dans le Chapitre 3, nous étudions la cordalité des graphes et nous introduisons la notion de k-Good décomposition arborescente. Nous étudions tout d’abord les jeux de Gendarmes et Voleur dans les graphes sans long cycle induit. Notre résultat principal est un algorithme polynomial qui, étant donné un graphe G, soit trouve un cycle induit de longueur au moins k+1, ou calcule une k-Good décomposition de G. Ces résultats ont été publiés à la conférence internationale ICALP’12 et dans la revue internationale Algorithmica. Dans la seconde partie de la thèse, nous nous concentrons sur des problèmes de routage. / A tree decomposition of a graph is a way to represent it as a tree by preserving some connectivity properties of the initial graph. Tree decompositions have been widely studied for their algorithmic applications, in particular using dynamic programming approach. In this thesis, we study tree decompositions satisfying various constraints and design algorithms to compute them in some graph classes. We then use tree decompositions or specific graph properties to solve several problems related to routing. The thesis is divided into two parts. In the first part, we study tree decompositions satisfying some properties. In Chapter 2, we investigate minimum size tree decompositions, i.e., with minimum number of bags. Given a fixed k 4, we prove it is NP-Hard to compute a minimum size decomposition with width at most k in the class of graphs with treewidth at least 4. We design polynomial time algorithms to compute minimum size tree decompositions in some classes of graphs with treewidth at most 3 (including trees). Part of these results will be presented in ICGT 2014. In Chapter 3, we study the chordality (longest induced cycle) of graphs and introduce the notion of good tree decomposition (where each bag must satisfy some particular structure). Precisely, we study the Cops and Robber games in graphs with no long induced cycles. Our main result is the design of a polynomial-Time algorithm that either returns an induced cycle of length at least k+1 of a graph G or compute a k-Good tree decomposition of G. These results have been published in ICALP 2012 and Algorithmica. In the second part of the thesis, we focus on routing problems.

No description available.

No description available.

Dans cette thèse, nous nous intéressons à diagnostiquer des systèmes intrinsèquement distribués (comme les systèmes pairs-à-pairs) où chaque pair n'a accès qu'à une sous partie de la description d'un système global. De plus, en raison d'une politique d'accès trop restrictive, il sera pourra qu'aucun pair ne puisse expliquer le comportement du système global. Dans ce contexte, le challenge du diagnostic distribué est le suivant: expliquer le comportement global d'un système distribué par un ensemble de pairs ayant chacun une vision limitée, tout comme l'aurait fait un unique pair diagnostiqueur ayant, lui, une vision globale du système.D'un point de vue théorique, nous montrons que tout nouveau système, logiquement équivalent au système pair-à-pairs initialement observé, garantit que tout diagnostic local d'un pair pourra être prolongé par un diagnostic global (dans ce cas, le nouveau système est dit correct pour le diagnostic distribué).Nous montrons aussi que si ce nouveau système est structuré (c-à-d: il contient un arbre couvrant pour lequel tous les pairs contenant une même variable forme un graphe connecté) alors il garantit que tout diagnostic global pourra être retrouvé à travers un ensemble de diagnostics locaux des pairs (dans ce cas le nouveau système est dit complet pour le diagnostic distribué).Dans un souci de représentation succincte et afin de respecter la politique de confidentialité du vocabulaire de chacun des pairs, nous présentons un nouvel algorithme Token Elimination (TE), qui décompose le système de pairs initial vers un système structuré.Nous montrons expérimentalement que TE produit des décompositions de meilleurs qualité (c-à-d: de plus petites largeurs arborescentes) que les méthodes envisagées dans un contexte distribué. À partir du système structuré construit par TE, nous transformons chaque description locale en une Forme Normale Disjonctive (FND) globalement cohérente.Nous montrons que ce dernier système garantit effectivement un diagnostic distribué correct et complet. En plus, nous exhibons un algorithme capable de vérifier efficacement que tout diagnostic local fait partie d'un diagnostic minimal global, faisant du système structuré de FNDs un système compilé pour le diagnostic distribué. / In this thesis, we focus on diagnosing inherently distributed systems such as peer-to-peer, where each peer has access to only a sub-part of the description of an overall system.In addition, due to a too restrictive access control policy, it can be possible that neither peer nor supervisor is able to explain the behaviour of the overall system.The goal of distributed diagnosis is to explain the behaviour of a distributed system by a set of peers (each having a limited local view) as a single diagnosis engine having a global view of the overall system.First, we show that any new system logically equivalent to the initially observed peer-to-peer setting ensures that all diagnosis of a peer may be extended to a global diagnosis (in this case the new system ensures correctness of the distributed diagnosis).Moreover, we prove that if the new system is structured (i.e.it contains a spanning tree for which all peers containing the same variable form a connected graph) then it ensures that any global diagnosis can be found through a set of local diagnoses (in this case the new system ensures the completeness of the distributed diagnoses).For a succinct representation and in order to comply with the privacy policy of the vocabulary of each peer, we present a new algorithm Token Elimination (TE), which decomposes the original peer system to a structured one.We experimentally show that TE produces better quality decompositions (i.e. smaller tree widths) than proposed methods in a distributed context.From the structured system built by TE, we transform each local description into globally consistent DNF.We demonstrate that the latter system is correct and complete for the distributed diagnosis.Finally, we present an algorithm that can effectively check that any local diagnosis is part of a global minimal diagnosis, turning the structured system of DNFs into a compiled system for distributed diagnosis.

L'alignement de macromolécules biologiques comme les protéines, l'ADN ou encore l'ARN est une problématique biologique et bio-informatique qui a pour but de révéler une partie des mystères du fonctionnement des cellules, constituants des êtres vivants. Les ARN non-codant sont des macromolécules intervenant dans le métabolisme de tout être vivant et les deux problématiques majeurs les concernant sont: la prédiction de leur structure pour mieux comprendre leur fonctionnement et leur détection dans des bases de données ou des génomes. L'une des approches: l'alignement structure-séquence d'ARN, répond à ces deux problématiques. Le problème d'alignement structure-séquence consiste à aligner une structure connue d'un premier ARN avec la séquence d'un deuxième ARN.La structure est représentée sous la forme d'un graphe ou de façon équivalente sous la forme d'une séquence arc-annotées et la séquence représente la suite des nucléotides de l'ARN.Pour résoudre ce problème, nous cherchons à optimiser l'alignement selon une fonction de coût. C'est donc un problème d'optimisation, qui malheureusement se révèle NP-Difficile.En conséquence différents travaux définissent des classes d'instances réduites pour lesquelles ils proposent des algorithmes spécifiques mais à complexités polynomiales.Les travaux de ma thèse unifient et la généralisent les approches précédentes par la construction d'un algorithme à complexité paramétrée non spécifique à une classe d'instances. En utilisant cet algorithme, il est possible de résoudre le problème d'alignement structure-séquence pour toutes les instances possibles, et aussi efficacement que les précédentes approches sur leur domaine de résolution respectif. Cet algorithme utilise une technique empruntée à la théorie des graphes: la décomposition arborescente, c'est-à-dire qu'il transforme la structure donnée en une décomposition arborescente et c'est ensuite cette décomposition qui est alignée avec la séquence donnée. L'alignement entre une décomposition arborescente et une séquence se fait par programmation dynamique.Sa mise en place a nécessité une reformulation du problème ainsi qu'une modification importante de l'utilisation classique de la programmation dynamique pour les décompositions arborescentes. Au final, cela conduit à un algorithme paramétré dont le paramètre est entièrement lié à la décomposition arborescente. La construction des décompositions arborescentes pour lesquelles l'alignement s'effectuera plus le efficacement possible est malheureusement un problème lui aussi NP-Difficile. Néanmoins, nous avons créé une heuristique de construction de décompositions adaptée aux structures d'ARN.Nous avons alors défini des nouvelles classes de structures pour lesquelles notre algorithme (décomposition et alignement) possède une faible complexité. Ces classes incluent notamment toutes les autres classes précédemment définies et la complexité de notre algorithme est au moins aussi faible que celles des algorithmes spécifiques sur leurs classes de structures respectives. Ces classes de structures représentent la majorité des structures connues et contiennent de nombreux éléments importants jusqu'alors non pris en compte (tel que les motifs tertiaires d'ARN). Le problème de l'alignement structure-séquence tente de répondre aux problématiques de prédictions de structures et de recherche d'ARN. Néanmoins, la qualité des résultats obtenus par sa résolution dépendent de la fonction de coût utilisée. Durant ma thèse j'ai commencé la mise place de la construction par apprentissage d'une nouvelle fonction de coût, adaptée aux nouvelles classes de structures que nous avons défini. Enfin de par la nature de l'algorithme, le travail réalisé permet des améliorations non négligeables, en terme de qualité des résultats et de rapidité de calcul comme la recherche de solution sous-optimales ou l'utilisation de l'algorithme au sein d'heuristiques dérivées d'heuristiques classiques. / The alignment of biological macromolecules such as proteins, DNA or RNA is a biological and bio-informatics problematic which aims to reveal some of the mysteries of how cells works. The non-coding RNA are involved in the metabolism of all living beings. The two major issues concerning them are: the prediction of their structure to better understand their function and their detection in databases or genomes. One approach, the structure-sequence alignment of RNA, addresses these two issues. The work done during my thesis provides some constructive elements on this problem and led me to call the graph algorithmic for its resolution. The alignment problem is to align a structure of a first RNA with the sequence of a second RNA. The structure on the first RNA is represented as a graph or equivalently as an arc-annotated sequence and the sequence represents the nucleotide sequence of the second RNA.To solve this problem, we aim to compute a minimal cost alignment, according to a given cost function. So, this is an optimization problem, which turns out to be NP-hard.Accordingly, different works define several reduced structure classes for which they propose specific algorithms but with polynomial complexity. The work of my thesis unifies and generalizes previous approaches by the construction of a unique (not class specific) parameterized algorithm. Using this algorithm, it is possible to solve the problem of structure-sequence alignment for all possible instances, and as effectively as previous approaches in their respective field of resolution.This algorithm uses a technique from graph theory: the tree decomposition, that is to say, it transforms the given structure into a tree-decomposition and the decomposition is then aligned with the sequence. The alignment between a tree-decomposition and a sequence is done by dynamic programming. Its implementation requires a reformulation of the problem as well as a substantial modifications to the conventional use of dynamic programming for tree decompositions. This leads to an algorithm whose parameter is entirely related to the tree-decomposition.The construction of tree decompositions for which the alignment is the most effective is unfortunately a NP-Hard problem. Nevertheless, we have developed a heuristic construction of decompositions adapted to RNA structures. We then defined new structure classes which extend existing ones without degrading the complexity of the alignment but which can represent the majority of known structures containing many important elements that had not be taken into account previously (such as RNA tertiary motifs).The sequence-structure alignment problem attempts to answer the problem of prediction of structures and RNA research. However, the quality of the results obtained by its resolution depends on the cost function. During my PhD I started to define new cost functions adapted to the new structure classes by a machine learning approach. Finally, the work allows significant improvements in terms of quality of results and computation. For example the approach directly allows the search for sub-optimal solutions or its use within heuristics derived from traditional heuristic methods.

對於任何一個圖G = (V;E) ，如果我們可以找到最少的k 個弦圖(V;Ei)，使得E = E1 \ \ Ek ，則我們定義此圖G = (V;E) 的chordality為k ；而一個圖G = (V;E) 的樹寬則被定義為此圖所有的樹分解的寬的最小值。在這篇論文中，最主要的結論是所有圖的chordality 會小於或等於它的樹寬；更特別的是，有一些平面圖的chordality 為3，而所有系列平行圖的chordality 頂多為2。 / The chordality of a graph G = (V;E) is dened as the minimum k such that we can write E = E1 \ \ Ek, where each (V;Ei) is a chordal graph. The treewidth of a graph G = (V;E) is dened to be the minimum width over all tree decompositions of G. In this thesis, the principal result is that the chordality of a graph is at most its treewidth. In particular, there are planar graphs with chordality 3, and series-parallel graphs have chordality at most 2.

L’importance des problèmes CSP, WCSP et #CSP est reflétée par la part considérable des travaux, théoriques et pratiques, dont ils font l’objet en intelligence artificielle et bien au-delà. Leur difficulté est telle qu’ils appartiennent respectivement aux classes NP-complet, NP-difficile et #P-complet. Aussi, les méthodes qui permettent de résoudre efficacement leurs instances ont une complexité en temps exponentielle. Les travaux de recherche de cette thèse se focalisent sur les méthodes de résolution exploitant la notion de décomposition arborescente. Ces méthodes ont suscité un vif intérêt de la part de la communauté scientifique du fait qu’elles soient capables de résoudre en temps polynomial certaines classes d’instances. Cependant, en pratique, elles n’ont pas encore montré toute leur efficacité vu la qualité de la décomposition employée ne prenant en compte qu’un critère purement structurel, sa largeur. Premièrement, nous proposons un nouveau cadre général de calcul de décompositions qui a la vertu de calculer des décompositions qui capturent des paramètres plus pertinents à l’égard de la résolution que la seule largeur de la décomposition. Ensuite, nous proposons une exploitation dynamique de la décomposition pendant la résolution pour les problèmes (W)CSP. Le changement de la décomposition pendant la résolution vise à adapter la décomposition selon la nature de l’instance. Finalement, nous proposons un nouvel algorithme de comptage qui exploite la décomposition d’une façon différente de celle des méthodes standards afin d’éviter des calculs inutiles.L’ensemble des contributions ont été évaluées et validées expérimentalement. / The importance of CSP, WCSP and #CSP problems is reflected by the considerableamount of theoretical and practical work of which they are subject in artificial intelligenceand far beyond. Their difficulty is such that they belong respectively to the NP-complete,NP-hard and #P-complete classes. Hence, the methods that are able to solve efficientlytheir instances have a complexity in exponential time. The research works of this thesisfocus on the solving methods exploiting the notion of tree-decomposition. These methodshave aroused a keen interest from the scientific community because they are able to solvesome classes of instances in polynomial time. Nevertheless, in practice, they have notshown yet their full efficiency given the quality of the used decomposition that takes onlyinto account a purely structural criterion, its width. First, we propose a new generic framework for computing decompositions which has the virtue of computing decompositionsthat capture more relevant parameters in the context of solving than the width. Then,we propose a dynamic exploitation of the decomposition during the solving for (W)CSPproblems. The modification of the decomposition during the solving aims to adapt the decomposition to the nature of the instance. Finally, we propose a new counting algorithmthat exploits the decomposition in a different way than standard methods in order toavoid unnecessary computations. All the contributions have been evaluated and validatedexperimentally.

Savoir comment transmettre une information est fondamental dans un réseau. Il est essentiel que chaque entité du réseau soit capable de décider localement, avec sa vue du réseau, du chemin par lequel l'information doit passer. Ainsi, il est souvent utile d'étudier la topologie du réseau, modélisée par un graphe, pour répondre à ces exigences. Nous nous intéressons dans un premier temps, à la décomposition arborescente des graphes planaires. En effet, comme dans beaucoup de problèmes de graphes, l'étude de la topologie des graphes nous conduit à procéder à une décomposition du graphe afin d'exploiter les propriétés structurelles qui en découlent. En suite, nous nous sommes aussi intéressés à la structure des graphes qui excluent un mineur H, en particulier le graphe K_{2,r}. Ces travaux nous ont permis d'améliorer les bornes actuelles connues sur la largeur arborescente de ces graphes. Dans la dernière partie, nous abordons le problème du routage compact. Nous nous sommes intéressés aux schémas de routage de plus courts chemins utilisant des adresses, des tables de routage de tailles optimales de O(log n) bits, où n est le nombre de sommets du graphe. Nous proposons un tel schéma de routage pour une famille de graphes valués contenant les arbres et les graphes planaire-extérieurs. / In a network, it is crucial to know how to construct an efficent routing scheme. It is fundamental for each entity with its local knowledge of the network, to be able to decide on which link to forward messages. Thus, it is important to sutdy the underlying network topology in order to design routing schemes. In the first part of this thesis, we construct a new tree-decomposition for planar graphs. In fact, as in many graph problems, the study of the graph structure leads to do a tree-decomposition for exploiting structural propertys of the graphs. In second part, we studied the structure of H-minor free graphs, in particular whenever H = K_{2,r}. Our results improve upon previous known bounds about the tree-width of K_{2,r}-minor free graphs. At last, we treat the problème of compact routing scheme. More precisely, we are interested in shortest-path routing schemes that use O(\log n) bits for addresses, headers and routing tables, where n is the number of vertices in the graph. We propose such a routing scheme for a large family of weighted graphs including outerplanar graphs.