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 syndrome de détresse respiratoire aiguë (SDRA) présente un taux de mortalité élevé, près de 40%, dans des unités de soins intensifs. Il est défini comme un ensemble de manifestations cliniques, radiologiques et physiologiques qui traduisent une intense inflammation pulmonaire et une hyperperméabilité pulmonaire, correspondant aux différentes agressions aiguës du poumon. Le prise en charge des patients atteints du SDRA nécessite une ventilation assistée qui, en cas de mauvaise adaptation des paramètres de ventilation, notamment, pression et volume, peut aggraver l'état du patient. Le réglage de ces paramètres est basé sur l'analyse de l'aération pulmonaire en réponse à la ventilation assistée. Cette analyse peut être faite sur des images tomodensitométriques (CT en anglais) après y avoir segmenté le parenchyme pulmonaire. Néanmoins, cette segmentation est entravée par l'augmentation de la densité du parenchyme, qui réduit le contraste entre le poumon et les structures voisines. Cette thèse cherche à fournir des outils de traitement d'images qui permettent aux experts l'analyse de l'aération pulmonaire dans des images CT acquises dans le cadre d'un projet sur le SDRA utilisant un modèle animal / Acute Respiratory Distress Syndrome (ARDS) is a life threatening disease presenting a high mortality of about 40% in intensive care units. It is the consequence of different pulmonary aggressions generating hypoxemia and pulmonary edema, which are radiologically expressed as infiltrations observable as opaque regions in the lung. The treatment of ARDS requires mechanical ventilation, which may deteriorate the state of the patient if the ventilation parameters, namely volume and pressure, are not correctly adjusted. To adjust the parameter settings to each individual case, lung aeration - in response to ventilation - needs to be assessed. This assessment can be done using computed tomography (CT) images. However, it requires the segmentation of the lung-parenchymal tissue, which is a challenging task in ARDS images due the opacities that hinder the image contrast. In this thesis we aim to provide the required tools for the experts to analyze the aeration in the images acquired within an ARDS project using an animal model