Les décompositions de graphes, lorsqu'elles sont de petite largeur, sont souvent utilisées pour résoudre plus efficacement des problèmes étant difficiles dans le cas de graphes quelconques. Dans ce travail de thèse, nous nous intéressons aux limites liées à ces décompositions, et à la construction d'obstructions certifiant leur grande largeur. Dans une première partie, nous donnons un algorithme généralisant et unifiant la construction d'obstructions pour différentes largeurs de graphes, en temps XP lorsque paramétré par la largeur considérée. Nous obtenons en particulier le premier algorithme permettant de construire efficacement une obstruction à la largeur arborescente en temps O^{tw+4}. La seconde partie de notre travail porte sur l'étude du problème Ensemble [Sigma,Rho]-Dominant, une généralisation des problèmes de domination sur les graphes et caractérisée par deux ensembles d'entiers Sigma et Rho. Les diverses études de ce problème apparaissant dans la littérature concernent uniquement les cas où le problème est FPT, lorsque paramétré par la largeur arborescente. Nous montrons que ce problème ne l'est pas toujours, et que pour certains cas d'ensembles Sigma et Rho, il devient W[1]-difficile lorsque paramétré par la largeur arborescente. Dans la dernière partie, nous étudions la complexité d'un nouveau problème de coloration appelé k-Coloration Additive, combinant théorie des graphes et théorie des nombres. Nous montrons que ce nouveau problème est NP-complet pour tout k >= 4 fixé, tandis qu'il peut être résolu en temps polynomial sur les arbres pour k quelconque et non fixé.

Dans cette étude, nous produisons une analyse des réseaux de transport publics (acronyme PTN en anglais) en combinant des outils de la théorie des réseaux complexes, des simulations numériques et des approches analytiques. Nous avons commencé par une analyse empirique des PTN de 14 villes importantes dans le monde et en avons déterminé les principales caractéristiques en termes de réseaux complexes. Cette apporche empirique montre que les PTN apparaissent comme des réseaux ("small world") fortement corrélés avec des "coefficients d'agrégation" élevés et des "distances les plus courtes moyennes" comparativement faibles. Nous avons ensuite introduit divers modèles de PTN à 1 et 2 dimensions. Le modèle de marches aléatoires auto-évitantes (SAW) en interactions mutuelles capture certaines des propriété statistiques des PTN dans les divers modes de représentation. Nous avons poursuivi cette étude en examinant la résistance des PTN à divers scénarios d'attaques, ce qui permet de définir des critères de robustesse des réseaux considérés.

Le concept de radio logicielle (SDR) est une solution pertinente pour concevoir des équipements multi-standards. Une façon de réaliser de tels équipements est d'identifier les fonctions et opérateurs communs entre les standards. Cette approche s'appelle la paramétrisation et est divisée en deux catégories : l'approche pragmatique qui est une version pratique pour créer et développer des opérateurs communs à partir d'opérateurs existants, et l'approche théorique dont l'objectif est de réaliser une exploration graphique d'un équipement multi-standards selon différents niveaux de granularité, accompagnée d'un problème d'optimisation. C'est cette dernière approche qui a constitué le sujet de base de cette thèse. Ainsi, une fonction de coût doit être optimisée afin de sélectionner les opérateurs communs entre les différentes normes, ce qui permet de proposer une configuration optimale à partir de laquelle sont déduits les opérateurs communs. Dans notre travail, nous avons dans un premier temps modélisé théoriquement la structure graphique d'un système multi-standards par un hypergraphe orienté. En outre, nous avons fourni une expression mathématique alternative de la fonction de coût suggérée, en utilisant des définitions propres à la théorie des graphes. Ensuite, nous avons montré que le problème d'optimisation associé était un problème NP sous une certaine contrainte, ce qui a entraîné une preuve d'exclusion de certaines configurations dont les coûts ne peuvent être minimaux. Ceci a constitué la deuxième contribution de cette thèse. Enfin, nous avons proposé un nouvel algorithme permettant de résoudre le problème d'optimisation donné, et dont l'intérêt est de donner une solution optimale du problème au lieu d'une solution approchée fournie par les méthodes heuristiques classiques. Un programme associé à cet algorithme a été développé en langage C, puis appliqué à plusieurs exemples de cas génériques afin d'en étudier les performances.

L'objectif de cette thèse est d'identifier et caractériser les boucles anatomiques et fonctionnelles cortico-sous-corticales chez l'Homme, à partir de données d'imagerie par résonance magnétique fonctionnelle (IRMf) au repos et de diffusion. Une boucle est un ensemble de régions corticales, sous-corticales et cérébelleuses, qui interagissent afin d'effectuer ou de préparer une tâche.Le premier axe de ce travail vise à identifier les réseaux fonctionnels cortico-sous-corticaux en IRMf au repos. Nous proposons une méthode statistique robuste séparant l'analyse corticale de l'analyse sous-corticale. Une analyse en composantes indépendantes spatiales est d'abord réalisée individuellement sur les régions corticales, et suivie d'une classification hiérarchique. Les régions sous-corticales associées sont ensuite extraites par un modèle linéaire général dont les régresseurs comportent la dynamique des régions corticales, suivi d'une analyse de groupe à effets aléatoires. La méthode est validée sur deux jeux de données différents. Un atlas immunohistochimique des structures sous-corticales permet ensuite de déterminer la fonction sensorimotrice, associative ou limbique des réseaux obtenus. Nous montrons enfin que l'anatomie est un support pour la fonction chez des sujets sains.Le dernier axe étudie le syndrome de Gilles de la Tourette, qu'on pense être dû à un dysfonctionnement des boucles cortico-sous-corticales. Nous caractérisons d'abord les boucles cortico-sous-corticales fonctionnelles grâce à des métriques d'intégration et de théorie des graphes, et des différences en termes de connectivité sont mises en évidence entre patients adultes et volontaires sains. Nous montrons également que les boucles cortico-sous-corticales fonctionnelles chez les patients sont soutenues par l'anatomie sous-jacente.

Nous proposons tout d'abord une étude de plusieurs problèmes de l'algorithmique distribuée. Nous fournissons un modèle formel appliqué aux réseaux de diffusion anonymes. Dans ce modèle, nous caractérisons les graphes dans lesquels il est possible de résoudre l'énumération et l'élection. Cette caractérisation se base sur la notion d'homomorphisme de graphes. Nous proposons deux algorithmes dont la complexité est polynomiale et qui améliorent les complexités exponentielles connues jusqu'à présent. Dans un second temps, nous étudions le problème du calcul de l'état global et nous introduisons la notion de weak snapshot. Nous montrons qu'il existe des solutions pour ce problème dans les réseaux anonymes. Nous présentons plusieurs résultats concernant le calcul de l'état global en liaison avec des applications telles que le calcul de points de reprise, la détection de la terminaison ou encore le calcul d'une cartographie du réseau. Dans un cadre plus pratique, nous présentons la conception, le développement et l'implémentation des algorithmes proposés pour le calcul de l'état global au sein du logiciel de simulation et de visualisation ViSiDiA.

Les travaux de cette thèse concernent la modélisation et l'optimisation de chaînes d’approvisionnement en biomasses pour de futures bio-raffineries. En effet, des chaînes d'approvisionnement efficaces sont essentielles pour fournir aux installations de conversion, de façon régulière, des quantités suffisantes de biomasse de qualité à des prix raisonnables. Le problème est tout d'abord décrit puis modélisé.Un modèle de réseau et un modèle de données sont ensuite développés pour permettre de décrire la structure de la chaîne d'approvisionnement et ses données, sans affecter le modèle mathématique sous-jacent. Ce dernier (MILP) combine pour la première fois divers aspects, soit originaux, soit gérés séparément dans la littérature. A partir des demandes de la raffinerie, une résolution exacte précise les activités logistiques dans le réseau et les équipements nécessaires, afin de minimiser le coût total composé des coûts de récoltes, de transport et de stockage. Des études de cas sont décrites pour illustrer ce modèle de planification tactique multi-biomasse et multi-période. Un modèle plus compact est aussi élaboré pour traiter des instances de très grandes tailles. Il est illustré par une étude de cas réelle pour une bio-raffinerie prévue près de Compiègne. Pour finir, les développements effectués pour la mise en place d’un prototype logiciel d’aide à la décision sont présentés et des recommandations d’un futur logiciel commercial sont proposées / The research works of this thesis address the problem of modeling and optimizing biomass supply chains for biorefineries. Indeed, efficient supply chains are essential to provide conversion facilities with sufficient quantities of quality biomass at reasonable prices. The problem is described and modeled.A network model and a data model are developed to allow to describe the structure of the supply chain and its data, without affecting the underlying mathematical model. The latter is a mixed-integer linear programming that combines for the first time various aspects, either original or tackled separately in the literature. For given refinery needs, its exact resolution by CPLEX specifies the logistic activities in the network (amounts harvested, baled, transported, stored etc.) and the necessary equipment, in order to minimize a total cost including harvesting costs, transport costs and storage costs. Case studies are described to illustrate this multi-biomass and multi-period tactical planning model.A more compact model is also elaborated to cope with large-scale instances. It is illustrated using a real case study for a bio-refinery planned near Compiègne, France.Finally, the developments conducted for the implementation of a prototype of decision-support application are presented and recommendations for coming to a commercial software are proposed

Le formalisme des états graphes consiste à modéliser des états quantiques par des graphes. Ce formalisme permet l'utilisation des notions et des outils de théorie des graphes (e.g. flot, domination, méthodes probabilistes) dans le domaine du traitement de l'information quantique. Ces dernières années, cette modélisation combinatoire a permis plusieurs avancées décisives, notamment (i) dans la compréhension des propriétés de l'intrication quantique (ii) dans l'étude des modèles de calcul particulièrement prometteurs en terme d'implémentation physique, et (iii) dans l'analyse et la construction de protocoles de cryptographie quantique. L'objectif de cette thèse est d'étudier les propriétés graphiques émergeant des problématiques d'informatique quantique, notamment pour la simulation quantique. En particulier, l'étude des propriétés de causalité et de localité des états graphes, en étendant par exemple la notion existante de flot de causalité à une notion intégrant des contraintes de localité, permettrait d'ouvrir de nouvelles perspectives pour la simulation de systèmes quantiques à l'aide d'états graphes. Des connections formelles avec les automates cellulaires quantiques bruités pourront également émerger de cette étude. / Graph States formalism consist in using graphs to model quantum states. This formalism allows us to use notion and tools of graph theory (e.g. flow, domination, probabilistic methods) in quantum information processing. Last years, this combinatorial modelisation had lead to many decisiv breakthroughs, in particular (i) in the comprehension of the quantum entranglement properties (ii) in very promising in term of physical implementation quantum calculus model, and (iii) in the analysis and construction of quantum cryptography protocols. The goal of this thesis is to study the graphic properties emerging of those quantum information processing problematics, especially for quantum simulation. In particular, the properties of causality and locality in graph states, by extanding for exemple the existing notion of causality flows to a notion integring the locality constraints, would allow new perspectives for the quantum system simulation using graphs states. Formal connections with noisy quantum cellular automata would emerge from this study.

La thèse étudie plusieurs problématiques centrales et actuelles de la finance moderne : la rationalité limitée des agents et leurs biais comportementaux vis-à-vis des valeurs nominales,le problème de la juste évaluation du prix des actions, la refonte du paysage de l'industrie post-négociation en Europe suite à l'introduction du projet de l'Euro système Target-2 Securities, ainsi que les modèles de défaut et les méthodes d’estimation des cycles de défaut pour un secteur donné. Les techniques employées sont variées: enquêtes sur données individuelles, économétrie, théorie des jeux, théorie des graphes, simulations de Monte-Carlo,chaînes de Markov cachées. Concernant l’illusion monétaire, les résultats confirment la robustesse des résultats d’études précédentes tout en dévoilant de nouvelles perspectives de recherche, par exemple tenter d’expliquer la disparité des réponses selon les caractéristiques individuelles des répondants,en particulier leur formation universitaire. L’étude du modèle de la Fed montre que la relation de long terme entre taux nominal des obligations d’Etat et rendement des actions n’est ni robuste, ni utile à la prédiction sur des horizons temporels réduits. L’étude sur Target 2 Securities a été confirmée par les faits. Enfin, le modèle d’estimation des défauts à partir de chaînes de Markov cachées fait preuve de bonnes performances dans un contexte européen, malgré la relative rareté des données pour sa calibration. / The thesis studies various themes that are central to modern finance : economic agents rationality and behavioural biases with respect to nominal values, the problem of asset fundamental valuation, the changing landscape of the European post-trade industry catalysed by the Eurosystem project Target 2 Securities, and models of defaults and methods to estimate defaults cycles for a given sector. Techniques employed vary: studies on individual data,econometrics, game theory, graph theory, Monte-Carlo simulations and hidden Markov chains. Concerning monetary illusion, results confirm those of previous study while emphasizing new areas for investigation concerning the interplay of individual characteristics, such as university education, and money illusion. The study of the Fed model shows that the long term relationship assumed between nominal government bond yield and dividend yield is neither robust, nor useful for reduced time horizons. The default model based on hidden Markov chains estimation gives satisfactory results in a European context, and this besides the relative scarcity of data used for its calibration.

Cette thèse se situe dans le domaine de graphes et de leurs applications, Elleest constitué de trois grandes parties, la première est consacrée à l’étude d’unnouveau type de coloration sommets distinguantes, les arête-colorations sommetsdistinguantespar écarte. Il consiste de trouver une valuation des arêtes qui permettede distinguer les sommets de graphes telle que chaque sommet v du graphe est identifiéde façon unique par la différence entre la plus grande et la plus petite des valeursincidentes à v. Le plus entier pour lequel le graphe G admet une arête-colorationsommets-distinguantes par écarte est le nombre chromatique par écart de G, notégap(G). Nous avons étudié ce paramètre pour diverses familles de graphes. Uneconjecture intéressante, proposée dans cette partie, suggère que le nombre chromatiquepar écart de tout graphe connexe d’ordre n > 2 vaut n - 1, n ou n + 1.La deuxième partie du manuscrit concerne le problème du placement de graphes.Nous proposons un état de l’art des problèmes de placement de graphes, puis nousintroduisons la nouvelle notion de placement de graphes étiquetés. Il s’agit d’unplacement de graphes qui préserve les étiquettes des sommets. Ensuite, nous proposonsdes encadrements de ce nouveau paramètre pour plusieurs classes de graphes.La troisième partie de la thèse s’intéresse au problème d’appariement d’arbres dansle cadre de la recherche d’information dans des documents structurés de type XML.Les algorithmes holistique de jointure structurelle est l’une des premières méthodesproposées pour résoudre l’appariement exact des documents XML. Ces algorithmessont souvent divisés en deux grandes étapes. La première étape permet de décomposerl’arbre de la requête en un ensemble de petites composantes connexes. Ensuite,des solutions intermédiaires pour chaque composante de la requête sont trouvées, cesrésultats intermédiaires sont joints pour obtenir la solution finale. Nous proposonsdans cette partie un nouvel algorithme appelé TwigStack++ qui vise principalementà diminuer le coût de la jointure et le calcule inutile recherche. Notre algorithmeobtient de meilleurs résultats en comparaison avec deux autres méthodes de l’étatde l’art. / In this thesis, we investigate some problems in graph theory, namelythe graph coloring problem, the graph packing problem and tree pattern matchingfor XML query processing. The common point between these problems is that theyuse labeled graphs.In the first part, we study a new coloring parameter of graphs called the gapvertex-distinguishing edge coloring. It consists in an edge-coloring of a graph G whichinduces a vertex distinguishing labeling of G such that the label of each vertex isgiven by the difference between the highest and the lowest colors of its adjacentedges. The minimum number of colors required for a gap vertex-distinguishing edgecoloring of G is called the gap chromatic number of G and is denoted by gap(G).We will compute this parameter for a large set of graphs G of order n and we evenprove that gap(G) 2 fn E 1; n; n + 1g.In the second part, we focus on graph packing problems, which is an area ofgraph theory that has grown significantly over the past several years. However, themajority of existing works focuses on unlabeled graphs. In this thesis, we introducefor the first time the packing problem for a vertex labeled graph. Roughly speaking,it consists of graph packing which preserves the labels of the vertices. We studythe corresponding optimization parameter on several classes of graphs, as well asfinding general bounds and characterizations.The last part deal with the query processing of a core subset of XML query languages:XML twig queries. An XML twig query, represented as a small query tree,is essentially a complex selection on the structure of an XML document. Matching atwig query means finding all the occurrences of the query tree embedded in the XMLdata tree. Many holistic twig join algorithms have been proposed to match XMLtwig pattern. Most of these algorithms find twig pattern matching in two steps. Inthe first one, a query tree is decomposed into smaller pieces, and solutions againstthese pieces are found. In the second step, all of these partial solutions are joinedtogether to generate the final solutions. In this part, we propose a novel holistictwig join algorithm, called TwigStack++, which features two main improvementsin the decomposition and matching phase. The proposed solutions are shown to beefficient and scalable, and should be helpful for the future research on efficient queryprocessing in a large XML database.

Durant cette thèse, nous nous sommes intéressés aux outils permettant d'extraire les propriétés structurelles et temporelles de réseaux dynamiques ainsi que les caractéristiques de certains scénarios de diffusion pouvant s'opérer sur ces réseaux. Nous avons travaillé sur un jeu de données spécifiques, issu du projet MOSAR, qui comporte entre autre le réseau de proximité des personnes au cours du temps durant 6 mois à l'hôpital de Berk-sur-mer. Ce réseau est particulier dans le sens où il est constitué de trois dimensions: temporelle, structurelle par la répartition des personnes en services et fonctionnelle car chaque personne appartient à une catégorie socio-professionnelle. Pour chacune des dimensions, nous avons utilisé des outils existants en physique statistique ainsi qu'en théorie des graphes pour extraire des informations permettant de décrire certaines propriétés du réseau. Cela nous a permis de souligner le caractère très structuré de la répartition des contacts qui suit la répartition en services et mis en évidence les accointances entre certaines catégories professionnelles. Concernant la partie temporelle, nous avons mis en avant l'évolution périodique circadienne et hebdomadaire ainsi que les différences fondamentales entre l'évolution des interactions des patients et celle des personnels. Nous avons aussi présenté des outils permettant de comparer l'activité entre deux périodes données et de quantifier la similarité de ces périodes. Nous avons ensuite utilisé la technique de simulation pour extraire des propriétés de diffusion de ce réseau afin de donner quelques indices pour établir une politique de prévention. / In this thesis, we focus on tools whose aim is to extract structural and temporal properties of dynamic networks as well as diffusion characteristics which can occur on these networks. We work on specific data, from the European MOSAR project, including the network of individuals proximity from time to time during 6 months at the Brek-sur-Mer Hospital. The studied network is notable because of its three dimensions constitution : the structural one induced by the distribution of individuals into distinct services, the functional dimension due to the partition of individual into groups of socio-professional categories and the temporal dimension.For each dimension, we used tools well known from the areas of statistical physics as well as graphs theory in order to extract information which enable to describe the network properties. These methods underline the specific structure of the contacts distribution which follows the individuals distribution into services. We also highlight strong links within specific socio-professional categories. Regarding the temporal part, we extract circadian and weekly patterns and quantify the similarities of these activities. We also notice distinct behaviour within patients and staff evolution. In addition, we present tools to compare the network activity within two given periods. To finish, we use simulations techniques to extract diffusion properties of the network to find some clues in order to establish a prevention policy.