Dans cette thèse, nous nous intéressons aux aspects algorithmiques et applications de deux problèmes de graphes, à savoir, la coloration et les alliances. La première partie concerne deux variantes de la coloration de graphes, la coloration Grundy et la coloration forte stricte. Nous commençons par l'étude du nombre Grundy des graphes réguliers. Nous donnons une condition fixe k, nous fournissons une condition nécessaire et suffisante pour que le nombre Grundy d'un graphe régulier soit au moins égal k. Nous caractérisons la classe des graphes cubiques (3-réguliers) pour laquelle le nombre Grundy est égal à 4, et nous présentons un algorithme linéaire pour déterminer le nombre Grundy d'un graphe cubique quelconque. Par ailleurs, en se basant sur la coloration forte stricte pour décomposer les arbres en petites composantes, nous présentons un nouvel algorithme pour l'appariement d'arbres étiquetés, non-ordonnés non-enracinés. Nous montrons que la distance calculée entre deux arbres est une pseudo-métrique. Nos expérimentations sur de larges bases synthétiques et des bases de données réelles confirment nos résultats analytiques et montrent que la distance proposée est précise et son algorithme est scalable. La seconde partie de cette thèse est consacrée aux alliances dans les graphes. Nous proposons un algorithme distribué autostabilisant pour la construction d'alliance offensive globale minimale dans un graphe arbitraire. Nous démontrons que cet algorithme converge sous le démon synchrone en temps linéaire. Ensuite, nous donnons le premier algorithme distribué autostabilisant pour le problème de l'alliance forte globale minimale dans un graphe quelconque. Nous prouvons que cet algorithme est polynomial sous le démon inéquitable distribué. Nous montrons par la suite, comment cet algorithme peut être adapté pour des généralisations du problème, comme la k-alliance forte et l'alliance forte pondérée. Enfin, en se basant sur les propriétés structurelles de l'alliance offensive, nous présentons une solution pour décentraliser le protocole de signalisation SIP. Ceci rend possible son déploiement dans un réseau mobile ad hoc / This thesis investigates the algorithmic aspects and applications of two graph problems, namely, colorings and alliances. In the first part, we focus on two variants of the proper vertex coloring, the Grundy coloring and the strict strong coloring. We start by the study of Grundy number for regular graphs. We give a sufficient condition for d-regular graphs with sufficiently large girth to have Grundy number equals d + 1. Then, using graph homomorphism, we obtain a necessary and sufficient condition for d-regular graphs to have Grundy number at least k. Moreover, we characterize cubic graphs (3-regular) for which the Grundy number is d + 1, and present a linear-time algorithm to determine the Grundy number of any arbitrary cubic graph. Subsequently, based on the strict strong coloring, we present an approach for the problem of matching labeled trees. Using this coloring, we propose a new algorithm to deterministically decompose a tree into small components. This leads to an efficient algorithm to measure an accurate distance between unrooted unordered labeled trees. The second part is devoted to the alliances in graphs. We first propose a linear-time self-stabilizing algorithm for the minimal global offensive alliance set problem, under the synchronous distributed scheduler. Then, we give the first self-stabilizing algorithm for the minimal global powerful alliance set problem in arbitrary graphs. Moreover, we show how this algorithm can be adapted to find the minimal global powerful k-alliance and the minimal weighted global powerful alliance sets. We prove that all these algorithms converge in polynomial-time under the unfair distributed scheduler. Finally, based on the structural properties of the offensive alliance, we propose a solution to decentralize the signaling protocol SIP. This enables SIP applications in mobile ad hoc networks

Le domaine de la modélisation du trafic routier vise à comprendre son évolution. Dans les dernières années, plusieurs modèles du trafic ont été proposés dans l’objectif de géolocaliser les embouteillages au sein du trafic, détecter des motifs dans le trafic routier, estimer l’état du trafic etc. La plupart des modèles proposés considèrent le trafic routier en termes de ses constituants ou comme une entité agrégée en fonction de l’échelle choisie et expliquent l’évolution du trafic quantitativement en tenant compte des relations entre les variables de trafic comme le flot, la densité et la vitesse. Ces modèles décrivent le trafic en utilisant des données très précises acquises par différents capteurs. La précision des données rend son calcul coûteux en termes de ressources requises. Une des solutions à ce problème est la représentation qualitative du trafic routier qui réduit le nombre de ressources de traitement nécessaires. Puisque le trafic routier est un phénomène spatio-temporel, les modèles proposés pour représenter ce type de phénomène pourraient être appliqués dans le cas du trafic routier. Les modèles spatio-temporels, proposés par la communauté de l’Analyse Spatio-Temporelle, ont comme objectif la représentation d’un phénomène tant du point de vue qualitatif que quantitatif. Certains de ces modèles proposent une discrétisation des phénomènes modélisés en considérant un phénomène comme constitué d’entités. Appliquée au trafic routier, cette notion permet d’identifier différentes entités, comme les véhicules, les piétons, les bâtiments etc., qui le constituent. Ces entités influent sur l’évolution du trafic. Les modèles spatio-temporels qualitatifs définissent l’effet des différentes entités les unes sur les autres en terme de relations spatiales. L’évolution spatio-temporelle du phénomène modélisé est représenté par la variation temporelle de ces relations. La prise en compte des entités du trafic et des relations spatiales formalise une structure qui peut être représentée en utilisant un graphe, où les nœuds modélisent des entités et les arcs des relations spatiales. Par conséquent, l’évolution du trafic, modélisée via ce graphe, devient l’évolution du graphe et peut être représenté en terme de la variation de la structure du graphe ainsi que celle des attributs de ses nœuds et de ses arcs. Dans cette thèse, nous proposons une modélisation du trafic routier de ce type basée sur la théorie des graphes. Une des applications à la modélisation du trafic routier est la détection des motifs pertinents au sein du trafic. Dans les modèles du trafic existants, les motifs détectés sont statistiques et sont représentés en utilisant des caractéristiques numériques. Le modèle que nous pro posons dans cette thèse met en avant la structure représentant le trafic routier et peut donc être utilisé pour définir des motifs structurels du trafic qui prennent en compte des différentes entités du trafic et leurs relations. Ces motifs structurels sont sous-jacents à une modélisation sous forme de graphe dynamique. Dans cette thèse, nous proposons un algorithme pour détecter ces motifs structurels du trafic dans le graphe spatio-temporel représentant le trafic routier. Ce problème est formalisé comme celui de l’isomorphisme de sous-graphe pour des graphes dynamiques. L’algorithme proposé est évalué en fonction desdifférents paramètres de graphes. / For past several decades, researchers have been interested in understanding traffic evolution, hence, have proposed various traffic models to identify bottleneck locations where traffic congestion occurs, to detect traffic patterns, to predict traffic states etc. Most of the existing models consider traffic as many-particle system, describe it using different scales of representation and explain its evolution quantitatively by deducing relations between traffic variables like flow, density and speed. Such models are mainly focused on computing precise information about traffic using acquired traffic data. However, computation of such precise information requires more processing resources. A way to remedy this problem is to consider traffic evolution in qualitative terms which reduces the required number of processing resources. Since traffic is spatio-temporal in nature, the models which deal with spatio-temporal phenomenon can be applied in case of traffic. Such models represent spatio-temporal phenomenon from qualitative as well as quantitative standpoints. Depending on the intended application, some models are able to differentiate between various entities taking part in the phenomenon, which proves useful in case of traffic since different objects like vehicles, buildings, pedestrians, bicycles etc., directly affecting traffic evolution, can be included in traffic models. Qualitative spatio-temporal models consider the effects of different entities on each other in terms of spatial relations between them and spatio-temporal evolution of the modeled phenomenon is described in terms of variation in such relations over time. Considering different traffic constituents and spatial relations between them leads to the formation of a structure which can be abstracted using graph, whose nodes represent individual constituents and edges represent the corresponding spatial relations. As a result, the evolution of traffic, represented using graph, is described in terms of evolution of the graph itself, i. e. change in graph structure and attributes of nodes and edges, with time. In this thesis, we propose such a graph model to represent traffic. As mentioned above, one of the applications of existing traffic models is in detecting traffic patterns. However, since such models consider traffic quantitatively, in terms of acquired traffic data, the patterns detected using such models are statistical (a term employed by Pattern Recognition researchers) in the sense that they are represented using numerical description. Since graph-based traffic model proposed in this thesis represents the structure of traffic, it can be employed to redefine the meaning of traffic patterns from statistical to structural (also a term from Pattern Recognition community). Structural traffic patterns include different traffic constituents and their inter-links and are represented using time-varying graphs. An algorithm to detect a given structural traffic pattern in the spatio-temporal graph representing traffic is proposed in this thesis. It formalizes this problem as subgraph isomorphism for time-varying graphs. In the end, the performance of the algorithm is tested using various graph parameters.

L'informatique en nuage (Cloud Computing) est un modèle à grande échelle et en évolution continue, permettant le provisionnement et l'utilisation des ressources informatiques à la demande, selon un modèle rentable de facturation à l'usage "pay-as-you-go". Ce nouveau paradigme a rapidement révolutionné l'industrie IT et a permis de nouvelles tendances en matière de prestation de services informatiques, y compris l'externalisation des infrastructures IT vers des prestataires tiers spécialisés. Cependant, la nature multi-utilisateur des plateformes d'hébergement, ainsi que la complexité des demandes, soulèvent plusieurs défis liés à la gestion des ressources Cloud. Malgré l'attention croissante portée à ce sujet, la plupart des efforts ont été axés sur des solutions centrées utilisateur, et malheureusement beaucoup moins sur les difficultés rencontrées par les fournisseurs pour maximiser leurs bénéfices. Dans ce contexte, la fédération de Cloud a été récemment proposée comme une solution clé pour répondre à l'augmentation et la fluctuation des charges de travail. Les fournisseurs ayant des besoins complémentaires en ressources au fil du temps, peuvent collaborer et partager leurs infrastructures respectives via l'externalisation ("Outsourcing") pour mieux satisfaire les demandes et exigences des utilisateurs. Cette thèse aborde le problème d'optimisation du profit via la fédération et l'allocation optimale des ressources parmi plusieurs fournisseurs d'infrastructures Cloud. L'étude examine les principaux défis et opportunités liés à la maximisation des revenus dans une fédération de Clouds, et définit des stratégies efficaces pour diriger les fournisseurs dans leurs décisions de coopération. Le but est de fournir des algorithmes qui automatisent la sélection du plan d'allocation le plus rentable, qui satisfait à la fois la demande des utilisateurs et les exigences de mise en réseau. Nous visons des modèles d'allocation génériques et robustes qui répondent aux nouvelles tendances Cloud, et de traiter les requêtes simples ainsi que complexes nécessitant le provisionnement de services composites avec différentes ressources distribuées et connectées. Conformément aux objectifs de la thèse, nous avons mené une étude approfondie des travaux antérieurs traitant la problématique de provisionnement des ressources d'infrastructure dans les environnements Cloud. L'analyse a porté notamment sur les modèles d'allocation ayant pour objectif la maximisation de profit et les lacunes et défis associés dans les fédérations de Clouds. Dans un deuxième temps, nous avons proposé un programme linéaire en nombre entiers (ILP), pour aider les fournisseurs de services dans leurs décisions de coopération via des actions optimales d'externalisation (outsourcing), d'internalisation (insourcing) et d'allocation en local. Ces différentes décisions d'allocation sont traitées conjointement dans une formule d'optimisation globale qui partitionne les graphes de requêtes entre les membres de la fédération, tout en satisfaisant les exigences de communication entre les services élémentaires. En plus de la topologie des graphes de ressources, ce partitionnement prend en compte les prix dynamiques et les quotas proposés par les membres de la fédération ainsi que les coûts d'hébergement des ressources et de leur mise en réseau. Enfin, nous avons proposé un algorithme heuristique pour améliorer les temps de convergence avec les instances de problèmes à grande échelle. L'approche proposée utilise un algorithme de "clustering" basé sur les arbres de Gomory-Hu pour le partitionnement des graphes et une stratégie de meilleur ajustement (Best-Fit matching) pour l'allocation et le placement des sous-graphes résultants. L'utilisation conjointe de ces deux techniques permet de capturer l'essence du problème d'optimisation et de respecter les différents objectifs fixés, tout en améliorant le temps de convergence vers les solutions quasi-optimales de plusieurs ordres de grandeur / Cloud computing is a steadily maturing large-scale model for providing on-demand IT resources on a pay-as-you-go basis. This emerging paradigm has rapidly revolutionized the IT industry and enabled new service delivery trends, including infrastructure externalization to large third-party providers. The Cloud multi-tenancy architecture raises several management challenges for all stakeholders. Despite the increasing attention on this topic, most efforts have been focused on user-centric solutions, and unfortunately much less on the difficulties encountered by Cloud providers in improving their business. In this context, Cloud Federation has been recently suggested as a key solution to the increasing and variable workloads. Providers having complementary resource requirements over time can collaborate and share their respective infrastructures, to dynamically adjust their hosting capacities in response to users' demands. However, joining a federation makes the resource allocation more complex, since providers have to also deal with cooperation decisions and workload distribution within the federation. This is of crucial importance for cloud providers from a profit standpoint and especially challenging in a federation involving multiple providers and distributed resources and applications. This thesis addresses profit optimization through federating and allocating resources amongst multiple infrastructure providers. The work investigates the key challenges and opportunities related to revenue maximization in Cloud federation, and defines efficient strategies to govern providers' cooperation decisions. The goal is to provide algorithms to automate the selection of cost-effective distributed allocation plans that simultaneously satisfy user demand and networking requirements. We seek generic and robust models able to meet the new trends in Cloud services and handle both simple and complex requests, ranging from standalone VMs to composite services requiring the provisioning of distributed and connected resources. In line with the thesis objectives, we first provide a survey of prior work on infrastructure resource provisioning in Cloud environments. The analysis mainly focuses on profit-driven allocation models in Cloud federations and the associated gaps and challenges with emphasis on pricing and networking issues. Then, we present a novel exact integer linear program (ILP), to assist IaaS providers in their cooperation decisions, through optimal "insourcing", "outsourcing" and local allocation operations. The different allocation decisions are treated jointly in a global optimization formulation that splits resource request graphs across federation members while satisfying communication requirements between request subsets. In addition to the request topology, this partitioning takes into account the dynamic prices and quotas proposed by federation members as well as the costs of resources and their networking. The algorithm performance evaluation and the identified benefits confirm the relevance of resource federation in improving providers' profits and shed light into the most favorable conditions to join or build a federation. Finally, a new topology-aware allocation heuristic is proposed to improve convergence times with large-scale problem instances. The proposed approach uses a Gomory-Hu tree based clustering algorithm for request graphs partitioning, and a Best-Fit matching strategy for subgraphs placement and allocation. Combining both techniques captures the essence of the optimization problem and meets the objectives, while speeding up convergence to near-optimal solutions by several orders of magnitude

L'objectif de réduction de la consommation en kérosène des avions passant par une plus grande efficacité des systèmes, la distribution électrique devient un moyen privilégié pour satisfaire les besoins. Dans ce cadre, la notion d'avion « plus électrique » implique de revoir les systèmes de distribution et d'étudier, notamment, le passage en haute tension continue(HVDC). Une description générale des systèmes embarqués sur les avions civils est donnée dans ce manuscrit ainsi qu'une description des avantages et inconvénients des différents vecteurs énergétiques permettant de mieux situer les gains envisageables lors du passage à l'électrification des systèmes. Cependant, la mise en place de la distribution HVDC peut entraîner de nouveaux problèmes, notamment de qualité et/ou d'instabilité. Afin de palier ces problèmes, une architecture est proposée dans laquelle les équipements sont reliés entre eux par des coeurs de distribution eux-mêmes liés par des organes de transferts de puissances pouvant maîtriser ces transferts: on parle alors de réseau maillé. Pour pouvoir réaliser ces transferts, deux types d'équipements électroniques de puissance sont proposés : le DCPFC (Direct Current Power Flow Controler) et le MAPFC (Mixed function for Actuation and Power Flow Control). Ces équipements imposent une gestion énergétique spécifique: il faut déterminer les modes de fonctionnement des équipements ainsi que les références des puissances à transférer. Pour cela, une modélisation du réseau sous forme de graphe est effectuée, ceci se traduisant par un algorithme générique permettant de déterminer les équations structurelles du réseau ainsi que deux algorithmes servant à contrôler des grandeurs distinctes: Les grandeurs discrètes sont contrôlées par un système expert détenant un ensemble de règles de fonctionnement ; Les grandeurs continues sont gérées par un algorithme de recherche de flot dans un graphe. Après la mise en place en simulation de l'ensemble du réseau maillé, un banc d'essai expérimental valide les principes décrits théoriquement et permet l'étude de différentes gestions énergétiques (tout autant qu'il permet de tester un équipement seul ou le réseau dans une configuration non-maillée). Finalement, une exploitation des concepts sur un réseau répondant aux normes aéronautiques est développée. Ceci posant notamment des problèmes aux niveaux de la conception des équipements mais également sur l'architecture actuelle des réseaux électriques (connexion du neutre des générateurs, protection des personnes, compatibilité électromagnétique, etc.).

Nous étudions la clôture algébrique et définissable dans les groupes libres. Les résultats principaux peuvent être résumés comme suit. Nous montrons un résultat de constructibilité des groupes hyperboliques sans torsion au-dessus de la clôture algébrique d'un sous-ensemble engendrant un groupe non abélien. Nous avons cherché à comprendre la place qu'occupe la clôture algébrique acl_G(A) dans certaines décompositions de G. Nous avons étudié la possibilité de la généralisation de la méthode de Bestvina-Paulin dans d'autres directions, en considérant les groupes de type fini qui agissent d'une manière acylindrique (au sens de Bowditch) sur les graphes hyperboliques. Enfin, nous avons étudié les relations qui existent entre les différentes notions de clôture algébrique et entre la clôture algébrique et la clôture définissable.

Dans la présente thèse nous étudions l'extraction d'arbres dans des graphes arêtes-coloriés.Nous nous concentrons sur la recherche d'arbres couvrants proprement arête-coloriés et faiblement arête-coloriés, notée PST et WST. Nous montrons que les versions d'optimisation de ces problèmes sont NP-Complete dans le cas général des graphes arêtes-coloriés, et nous proposons des algorithmes pour trouver ces arbres dans le cas des graphes arêtes-coloriés sans cycles proprement arêtes-coloriés.Nous donnons également quelques limites de nonapproximabilité. Nous proposons des conditions suffisantes pour l'existence de la PST dans des graphes arêtes-coloriés (pas forcément propre), en fonction de différents paramètres de graphes, tels que : nombre total de couleurs, la connectivité et le nombre d'arêtes incidentes dedifférentes couleurs pour un sommet. Nous nous intéressons aux chemins hamiltoniens proprement arêtes-coloriés dans le casdes multigraphes arêtes-coloriés. Ils présentent de l'intérêt pour notre étude, car ce sontégalement des arbres couvrants proprement arêtes-coloriés. Nous établissons des conditions suffisantes pour qu'un multigraphe contienne un chemin hamiltonien proprement arêtes-coloriés, en fonction de plusieurs paramètres tels que le nombre d'arêtes, le degré d'arêtes, etc. Puisque l'une des conditions suffisantes pour l'existence des arbres couvrants proprement arêtes-coloriés est la connectivité, nous prouvons plusieurs bornes supérieures pour le plus petit nombre de couleurs nécessaires pour la k-connectivité-propre. Nous énonçons plusieurs conjectures pour les graphes généraux et bipartis, et on arrive à les prouver pour k = 1.

.

.

Quelques algorithmes entre le monde des graphes et les nuages de points.

Le co-clustering est une technique de classification consistant à réaliser une partition simultanée des lignes et des colonnes d'une matrice de données. Parmi les approches existantes, MODL permet de traiter des données volumineuses et de réaliser une partition de plusieurs variables, continues ou nominales. Nous utilisons cette approche comme référence dans l'ensemble des travaux de la thèse et montrons la diversité des problèmes de data mining pouvant être traités, comme le partitionnement de graphes, de graphes temporels ou encore le clustering de courbes. L'approche MODL permet d'obtenir des résultats fins sur des données volumineuses, ce qui les rend difficilement interprétables. Des outils d'analyse exploratoire sont alors nécessaires pour les exploiter. Afin de guider l'utilisateur dans l'interprétation de tels résultats, nous définissons plusieurs outils consistant à simplifier des résultats fins afin d'en avoir une interprétation globale, à détecter les clusters remarquables, à déterminer les valeurs représentatives de leurs clusters et enfin à visualiser les résultats. Les comportements asymptotiques de ces outils d'analyse exploratoire sont étudiés afin de faire le lien avec les approches existantes. Enfin une application sur des comptes-rendus d'appels de l'opérateur Orange, collectés en Côte d'Ivoire, montre l'intérêt de l'approche et des outils d'analyse exploratoire dans un contexte industriel.