Soit G = (V, E) un graphe simple fini. Soit (a, b) un couple d’entiers positifs. On note par τ(G) le nombre de sommets d’un chemin d’ordre maximum dans G. Une partition (A,B) de V(G) est une (a,b)−partition si τ(⟨A⟩) ≤ a et τ(⟨B⟩) ≤ b. Si G possède une (a, b)−partition pour tout couple d’entiers positifs satisfaisant τ(G) = a+b, on dit que G est τ−partitionnable. La conjecture de partitionnement des chemins, connue sous le nom anglais de Path Partition Conjecture, cherche à établir que tout graphe est τ−partitionnable. Elle a été énoncée par Lovász et Mihók en 1981 et depuis, de nombreux chercheurs ont tenté de démontrer cette conjecture et plusieurs y sont parvenus pour certaines classes de graphes. Le présent mémoire rend compte du statut de la conjecture, en ce qui concerne les graphes non-orientés et ceux orientés. / Let G = (V,E) be a finite simple graph. We denote the number of vertices in a longest path in G by τ(G). A partition (A,B) of V is called an (a,b)−partition if τ(⟨A⟩) ≤ a and τ(⟨B⟩) ≤ b. If G can be (a,b)−partitioned for every pair of positive integers (a, b) satisfying a + b = τ (G), we say that G is τ −partitionable. The following conjecture, called The Path Partition Conjecture, has been stated by Lovász and Mihók in 1981 : every graph is τ−partitionable. Since that, many researchers prove that this conjecture is true for several classes of graphs and digraphs. This study summarizes the different results about the Path Partition conjecture.

Mémoire numérisé par la Direction des bibliothèques de l'Université de Montréal.

Les travaux présentés dans cette thèse effectuée au LaBRI portent sur la mise en place d’une flotte de drones et le portage sur celle-ci d’applications collaboratives distribuées utilisant des communications asynchrones non sûres. Ces applications sont formalisées grâce au modèle de réétiquetage de graphes Asynchronous Dynamicity Aware Graph Relabeling System (ADAGRS) que nous proposons. Au delà des contributions théoriques, ces travaux ont débouché sur la mise en place du démonstrateur CARUS dans lequel cinq drones se partagent la surveillance d'une grille de 15 points d’incidents potentiels (au sol).Lorsqu’un drone détecte un incident, il s'en rapproche pour le traiter. Le reste de la flotte doit alors prendre en charge les points que ce drone ne traite plus.Les réorganisations nécessaires de la flotte se font en totale autonomie vis-à-vis du sol et sous hypothèse de perte éventuelle de drones et de messages. / The work presented in this thesis, carried out at LaBRI, deals with the set up of a fleet of UAVs and the porting on it of distributed collaborative applications that use unsafe asynchronous communications. These applications are modeled with Asynchronous Dynamicity Aware Graph Relabeling System (ADAGRS), the formal model based on graph relabellings that we propose.Beyond the theoretical contributions, this work led to the development of the CARUS demonstrator in which five UAVs share the supervision of a grid of 15 points of potential ground incidents.When a UAV detects an incident, it comes close to it in order to deal with it. The rest of the fleet must then take care of the points that this UAV no longer visits.The necessary reorganizations of the fleet are done in total autonomy with respect to the ground and under the hypothesis of possible loss of UAVs and messages.

Nous détaillons dans cette thèse des algorithmes modérément exponentiels pour l'approximation du problème MAX SAT. Nous discutons d'une méthode générique pour la conception d'algorithmes exponentiels réalisant des schémas d'approximation dans un cadre plus général. Enfin, nous présentons des résultats paramétrés pour des problèmes de coupe à cardinalité contrainte. / We give in this thesis some moderately exponential algorithms for the MAX SAT problem. We discuss a very general method to conceive efficient exponential algorithms that give approximation scheme. In the end, we present some parameterized results for CUT problem with constrained cardinality.

Les travaux de cette thèse portent sur la reconnaissance des indices textuels dans les images et les vidéos. Dans ce cadre, nous avons conçu des prototypes d'OCR (optical character recognition) capables de reconnaître tant des textes incrustés que des textes de scène acquis n'importe où au sein d'images ou de vidéos. Nous nous sommes intéressée à la définition d'approches robustes à la variabilité des textes et aux conditions d'acquisition. Plus précisément, nous avons proposé deux types de méthodes dédiées à la reconnaissance de texte : - une approche fondée sur une segmentation en caractères qui recherche des séparations non linéaires entre les caractères adaptées à la morphologie de ces derniers ; - deux approches se passant de la segmentation en intégrant un processus de scanning multi-échelles ; la première utilise un modèle de graphe pour reconnaître les textes tandis que la seconde intègre un modèle connexionniste récurrent spécifiquement développé pour gérer les contraintes spatiales entre les caractères.Outre les originalités de chacune des approches, deux contributions supplémentaires de ce travail résident dans la définition d'une reconnaissance de caractères fondée sur un modèle de classification neuronale et l'intégration de certaines connaissances linguistiques permettant de tirer profit du contexte lexical. Les différentes méthodes conçues ont été évaluées sur deux bases de documents : une base de textes incrustés dans des vidéos et une base publique de textes de scène. Les expérimentations ont permis de montrer la robustesse des approches et de comparer leurs performances à celles de l'état de l'art, mettant en évidence leurs avantages et leurs limites. / This thesis focuses on the recognition of textual clues in images and videos. In this context, OCR (optical character recognition) systems, able to recognize caption texts as well as natural scene texts captured anywhere in the environment have been designed. Novel approaches, robust to text variability (differentfonts, colors, sizes, etc.) and acquisition conditions (complex background, non uniform lighting, low resolution, etc.) have been proposed. In particular, two kinds of methods dedicated to text recognition are provided:- A segmentation-based approach that computes nonlinear separations between characters well adapted to the localmorphology of images;- Two segmentation-free approaches that integrate a multi-scale scanning scheme. The first one relies on a graph model, while the second one uses a particular connectionist recurrent model able to handle spatial constraints between characters.In addition to the originalities of each approach, two extra contributions of this work lie in the design of a character recognition method based on a neural classification model and the incorporation of some linguistic knowledge that enables to take into account the lexical context.The proposed OCR systems were tested and evaluated on two datasets: a caption texts video dataset and a natural scene texts dataset (namely the public database ICDAR 2003). Experiments have demonstrated the efficiency of our approaches and have permitted to compare their performances to those of state-of-the-art methods, highlighting their advantages and limits.

Une nouvelle borne supérieure sur le cardinal des codes de sous-espaces d'un espace vectoriel fini est établie grâce à la méthode de la programmation semidéfinie positive. Ces codes sont d'intérêt dans le cadre du codage de réseau (network coding). Ensuite, par la même méthode, l'on démontre une borne sur le cardinal des ensembles qui évitent une distance donnée dans l'espace de Johnson et qui est obtenue par une variante d'un programme de Schrijver. Les résultats numériques permettent d'améliorer les bornes existantes sur le nombre chromatique mesurable de l'espace Euclidien. Une hiérarchie de programmes semidéfinis positifs est construite à partir de certaines matrices issues des complexes simpliciaux. Ces programmes permettent d'obtenir une borne supérieure sur le nombre d'indépendance d'un graphe. Aussi, cette hiérarchie partage certaines propriétés importantes avec d'autres hiérarchies classiques. A titre d'exemple, le problème de déterminer le nombre d'indépendance des graphes de Paley est analysé. / We apply the semidefinite programming method to obtain a new upper bound on the cardinality of codes made of subspaces of a linear vector space over a finite field. Such codes are of interest in network coding.Next, with the same method, we prove an upper bound on the cardinality of sets avoiding one distance in the Johnson space, which is essentially Schrijver semidefinite program. This bound is used to improve existing results on the measurable chromatic number of the Euclidean space.We build a new hierarchy of semidefinite programs whose optimal values give upper bounds on the independence number of a graph. This hierarchy is based on matrices arising from simplicial complexes. We show some properties that our hierarchy shares with other classical ones. As an example, we show its application to the problem of determining the independence number of Paley graphs.

Dans les réseaux énergétiques, la connaissance des équipements, leurs emplacements et leursfonctions sont les prérequis à l’exploitation de l’infrastucture. En effet, tout opérateur disposed’une carte appelée schéma synoptique indiquant les connexions entre les équipements. À partirde cette carte, sont prises des décisions pour un fonctionnement optimal du réseau.Ce schéma synoptique peut être érronné parce que des opérations de maintenance sur le réseaun’auraient pas été retranscrites ou mal saisies. Et cela peut entrainer des coûts supplémentairesd’exploitation du réseau énergetique.Nous considérons le réseau électrique d’un Datacenter. Ce réseau est composé d’une topologiephysique modélisée par un DAG sans circuit et de mesures électriques sur ces arcs. La particularitéde ce réseau est que les mesures contiennent des erreurs et cette topologie est inconnue c’est-à-direles arcs sont connus mais les extrémités des arcs sont inconnues. Dans le cas où ces mesuressont correctes alors la corrélation des arcs induit la matrice d’adjacence du line-graphe du graphenon-orienté sous-jacent de notre DAG. Un line-graphe est un graphe dans lequel chaque sommet etson voisinage peuvent être partitionnés par une ou deux cliques et que chaque arête est couvertepar une clique. Cependant, avec la présence des erreurs de mesures, nous avons un graphe avecdes arêtes en plus ou en moins qui n’est pas nécessairement un line-graphe. Si ce graphe est unline-graphe alors il n’est pas le line-graphe de notre DAG. Notre problème est de découvrir cettetopologie en se basant sur ces mesures électriques.Nous débutons par une étude bibliographique des corrélations de mesures possibles afin dedéterminer celle qui est pertinente pour notre problème. Ensuite nous proposons deux algorithmespour résoudre ce problème. Le premier algorithme est l’algorithme de couverture et il déterminel’ensemble des cliques qui couvre chaque sommet de notre graphe. Le second algorithme estl’algorithme de correction. Il ajoute ou supprime des arêtes au voisinage d’un sommet non couvertde telle sorte que son voisinage soit partitionné en une ou deux cliques. Enfin, nous évaluons lesperformances de nos algorithmes en vérifiant le nombre d’arêtes corrigées et la capacité à retournerle graphe le plus proche du line-graphe de notre DAG. / In energy network, the knowledge of equipments, their locations and their functions are theimportant information for the distributor service operator. In fact, each operator has a networkplan often named synoptic schema. That schema shows the interconnexion between equipments inthe network. From this schema, some management decisions have taken for ensuring an optimalperformance of a network.Sometimes, a synoptic schema has some mistakes because the maintenance operations, such aschanged the connexion between equipments or replaced equipments, have not been updated orhave been written with errors. And these mistakes increase exploitation cost in the energy network.We consider an electric network of a datacenter. This network consists of physical topologymodelised by a DAG without circuit and measurements are on the edges of a DAG. The mainpoint of the network is that measurements are some mistakes and the topology is unknown i.ewe know edges but the nodes of edges are unknown. When measurements are correct then thecorrelations between pairwise edges provide the adjacency matrix of the linegraph of undirectedgraph of the DAG. A linegraph is a graph in which each node and the neighbor are partitionnedby one or deux cliques. However, with the mistakes in measurements, the obtained graph is nota linegraph because it contains more or less edges. If the obtained graph is a linegraph then it isa linegraph of the other DAG. Our problem is to discovery the topology of the DAG with somemistakes in measurements.We start by the state of art in the measurement correlations in order to choose the good methodfor our problem. Then, we propose two algorithms to resolve our problem. The first algorithmis the cover algorithm and it returns the set of cliques in the graph. The second algorithm is acorrection algorithm which adds or deletes edges in the graph for getting a nearest linegraph ofthe DAG. In the last, we evaluate the performances of the algorithms by checking the number ofedges corrected and the ability to return a nearest linegraph of the DAG.

Cette thèse s’intéresse à une problématique ayant de nombreuses applications pratiques, à savoir la comparaison automatique d’objets et l’évaluation de la similarité. Lorsque les objets sont modélisés par des graphes, ce problème de comparaison automatique d’objets se ramène à un problème d’appariement de graphes, c’est-à-dire, chercher une mise en correspondance entre les sommets des graphes permettant de retrouver le plus grand nombre de caractéristiques communes. Différentes classes existent allant de la plus restrictive à la plus générale. Dans la plus restrictive isomorphisme de (sous-) graphes, il s’agit de chercher un appariement exact entre les sommets des graphes de manière à prouver que les deux graphes possèdent une structure identique ou que l’un d’eux est inclus dans l’autre, un sommet étant apparié avec au plus un sommet. Dans la plus générale (appariement multivoque), l’objectif n’est plus de trouver un appariement exact mais le meilleur appariement, c’est-à-dire, celui qui préserve un maximum de sommets et d’arcs, un sommet pouvant être apparié à un ensemble de sommets. Nous nous intéressons au problème de la recherche du meilleur appariement multivoque, ce problème étant plus général que les problèmes d’appariement restrictifs. Sa résolution est clairement un défi tant par la difficulté du problème que par l’importance de ses applications. Pour relever ce défi, nous proposons d’étudier les capacités de l’optimisation par colonies de fourmis (ACO). Notre étude est menée dans deux contextes : un contexte statique, où le problème est figé, et un contexte dynamique, où les graphes à comparer, les contraintes à respecter ainsi que les critères définissant la qualité des appariements changent régulièrement de sorte que la solution doit être dynamiquement adaptée. Un premier objectif, de cette thèse, est de proposer l’algorithme ACO générique pour la résolution des problèmes d’appariement de graphes. Plusieurs points clés sont étudiés dans cet algorithme, à savoir : l’influence des paramètres sur la qualité des solutions construites, l’influence de la stratégie phéromonale et du facteur heuristique, et l’hybridation avec une technique de recherche locale. Un deuxième objectif est de proposer un algorithme ACO générique pour résoudre des problèmes d’optimisation dynamiques. L’algorithme proposé est appliqué et expérimenté à quelques problèmes dynamiques, à savoir : l’appariement de graphes, le problème du sac à dos multidimensionnel, et le voyageur de commerce / The thesis addresses the problematic of comparing objects and similarity measuring. If objects are described by graphs, so that measuring objects similarity turns into determining graph similarity, i.e., matching graph vertices to identify their common features and their differences. Different classes of graph matching have been proposed going on the most restrictive ones to the most general. In restrictive graph matching (graph or sub-graph isomorphism), the objective is to show graph equivalence or inclusion, a vertex in a graph may be matched with one vertex at most on the other graph. In general graph matching (multivalent matching), the goal is not yet to find an “exact” matching (a matching which preserves all vertices and edges), but to look for a “best” matching (a matching which preserves a maximum number of vertices and edges), a vertex in one graph may be matched with a set of vertices in the other graph. In our work, we consider the problem of searching the best multivalent matching which is a NP-hard optimization problem. More precisely, we propose to investigate the ability if the ant colony optimization meta-heuristic (ACO). Two cases are considered in our study: the static case where the problem remains invariant through time and the dynamic case where graphs to compare constrained to satisfy and the criterions defining matching quality may change over the time, so that solutions must be dynamically adapted to the changes. A first goal of this thesis is to propose a generic ACO algorithm for solving graph matching problems. Different key points, like the pheromonal strategy to be used, the heuristic factor and the use of a local search procedure, are studied. A second goal of this work is to propose a generic ACO algorithm for solving dynamic optimization problems. The proposed algorithm will be applied and experimentally studied on three different dynamic problems: graph matching problem, multi-dimensional knapsack problem and the travelling salesman problem

Ce travail de thèse concerne la fouille de données sur des graphes attribués. Il s'agit de graphes dans lesquels des propriétés, encodées sous forme d'attributs, sont associées à chaque sommet. Notre objectif est la découverte, dans ce type de données, de sous-graphes organisés en plusieurs groupes de sommets fortement connectés et homogènes au regard des attributs. Plus précisément, nous définissons l'extraction sous contraintes d'ensembles de sous-graphes densément connectés et tels que les sommets partagent suffisamment d'attributs. Pour cela nous proposons deux familles de motifs originales ainsi que les algorithmes justes et complets permettant leur extraction efficace sous contraintes. La première famille, nommée Ensembles Maximaux de Cliques Homogènes, correspond à des motifs satisfaisant des contraintes concernant le nombre de sous-graphes denses, la taille de ces sous-graphes et le nombre d'attributs partagés. La seconde famille, nommée Collections Homogènes de k-cliques Percolées emploie quant à elle une notion de densité plus relaxée permettant d'adapter la méthode aux données avec des valeurs manquantes. Ces deux méthodes sont appliquées à l'analyse de deux types de réseaux, les réseaux de coopérations entre chercheurs et les réseaux d'interactions de protéines. Les motifs obtenus mettent en évidence des structures utiles dans un processus de prise de décision. Ainsi, dans un réseau de coopérations entre chercheurs, l'analyse de ces structures peut aider à la mise en place de collaborations scientifiques entre des groupes travaillant sur un même domaine. Dans le contexte d'un graphe de protéines, les structures exhibées permettent d'étudier les relations entre des modules de protéines intervenant dans des situations biologiques similaires. L'étude des performances en fonction de différentes caractéristiques de graphes attribués réels et synthétiques montre que les approches proposées sont utilisables sur de grands jeux de données. / The work presented in this thesis deals with data mining approaches for the analysis of attributed graphs. An attributed graph is a graph where properties, encoded by means of attributes, are associated to each vertex. In such data, our objective is the discovery of subgraphs formed by several dense groups of vertices that are homogeneous with respect to the attributes. More precisely, we define the constraint-based extraction of collections of subgraphs densely connected and such that the vertices share enough attributes. To this aim, we propose two new classes of patterns along with sound and complete algorithms to compute them efficiently using constraint-based approaches. The first family of patterns, named Maximal Homogeneous Clique Set (MHCS), contains patterns satisfying constraints on the number of dense subgraphs, on the size of these subgraphs, and on the number of shared attributes. The second class of patterns, named Collection of Homogeneous k-clique Percolated components (CoHoP), is based on a relaxed notion of density in order to handle missing values. Both approaches are used for the analysis of scientific collaboration networks and protein-protein interaction networks. The extracted patterns exhibit structures useful in a decision support process. Indeed, in a scientific collaboration network, the analysis of such structures might give hints to propose new collaborations between researchers working on the same subjects. In a protein-protein interaction network, the analysis of the extracted patterns can be used to study the relationships between modules of proteins involved in similar biological situations. The analysis of the performances, on real and synthetic data, with respect to different attributed graph characteristics, shows that the proposed approaches scale well for large datasets.

Pour l’apprentissage automatisé de données régulières comme des images ou des signaux sonores, les réseaux convolutifs profonds s’imposent comme le modèle de deep learning le plus performant. En revanche, lorsque les jeux de données sont irréguliers (par example : réseaux de capteurs, de citations, IRMs), ces réseaux ne peuvent pas être utilisés. Dans cette thèse, nous développons une théorie algébrique permettant de définir des convolutions sur des domaines irréguliers, à l’aide d’actions de groupe (ou, plus généralement, de groupoïde) agissant sur les sommets d’un graphe, et possédant des propriétés liées aux arrêtes. A l’aide de ces convolutions, nous proposons des extensions des réseaux convolutifs à des structures de graphes. Nos recherches nous conduisent à proposer une formulation générique de la propagation entre deux couches de neurones que nous appelons la contraction neurale. De cette formule, nous dérivons plusieurs nouveaux modèles de réseaux de neurones, applicables sur des domaines irréguliers, et qui font preuve de résultats au même niveau que l’état de l’art voire meilleurs pour certains. / Convolutional neural networks have proven to be the deep learning model that performs best on regularly structured datasets like images or sounds. However, they cannot be applied on datasets with an irregular structure (e.g. sensor networks, citation networks, MRIs). In this thesis, we develop an algebraic theory of convolutions on irregular domains. We construct a family of convolutions that are based on group actions (or, more generally, groupoid actions) that acts on the vertex domain and that have properties that depend on the edges. With the help of these convolutions, we propose extensions of convolutional neural netowrks to graph domains. Our researches lead us to propose a generic formulation of the propagation between layers, that we call the neural contraction. From this formulation, we derive many novel neural network models that can be applied on irregular domains. Through benchmarks and experiments, we show that they attain state-of-the-art performances, and beat them in some cases.