La coloration de graphes est un problème central de l’optimisation combinatoire. C’est un domaine très attractif par ses nombreuses applications. Différentes variantes et généralisations du problème de la coloration de graphes ont été proposées et étudiées. La coloration d’arêtes d’un graphe consiste à attribuer une couleur à chaque arête du graphe de sorte que deux arêtes ayant un sommet commun n’ont jamais la même couleur, le tout en utilisant le moins de couleurs possibles. Dans la première partie de cette thèse, nous étudions le problème de la coloration d’arêtes ℓ-distance, qui est une généralisation de la coloration d’arêtes classique. Nous menons une étude combinatoire et algorithmique du paramètre. L’étude porte sur les classes de graphes suivantes : les chaines, les grilles, les hypercubes, les arbres et des graphes puissances. Le paramètre de la coloration d’arêtes ℓ-distance permet de modéliser des problèmes dans des réseaux assez grands. Cependant, avec la multiplication du nombre de nœuds, les réseaux sont de plus en plus vulnérables aux défaillances (ou pannes). Dans la deuxième partie, nous nous intéressons aux algorithmes tolérants aux pannes et en particulier les algorithmes auto-stabilisants. Nous proposons un algorithme auto-stabilisant pour la coloration propre d’arêtes. Notre solution se base sur le résultat de vizing pour utiliser un minimum de couleurs possibles. Par la suite, nous proposons un algorithme auto-stabilisant de clustering destine a des applications dans le domaine de la sécurité dans les réseaux mobiles Ad hoc. La solution que nous proposons est un partitionnement en clusters base sur les relations de confiance qui existent entre nœuds. Nous proposons aussi un algorithme de gestion de clés de groupe dans les réseaux mobiles ad hoc qui s’appuie sur la topologie de clusters préalablement construite. La sécurité de notre protocole est renforcée par son critère de clustering qui surveille en permanence les relations de confiance et expulse les nœuds malveillants de la session de diffusion. / Graph coloring is a famous combinatorial optimization problem and is very attractive for its numerous applications. Many variants and generalizations of the graph-coloring problem have been introduced and studied. An edge-coloring assigns a color to each edge so that no two adjacent edges share the same color. In the first part of this thesis, we study the problem of the ℓ-distance-edge-coloring, which is a generalization of the classical edge-coloring. The study focuses on the following classes of graphs : paths, grids, hypercubes, trees and some power graphs. We are conducting a combinatorial and algorithmic study of the parameter. We give a sequential coloring algorithm for each class of graph. The ℓ-distance-edge-coloring is especially considered in large-scale networks. However, with the increasing number of nodes, networks are increasingly vulnerable to faults. In the second part, we focus on fault-tolerant algorithms and in particular self-stabilizing algorithms. We propose a self-stabilizing algorithm for proper edge-coloring. Our solution is based on Vizing’s result to minimize number of colors. Subsequently, we propose a selfstabilizing clustering algorithm for applications in the field of security in mobile ad hoc networks. Our solution is a partitioning into clusters based on trust relationships between nodes. We also propose a group key-management algorithm in mobile ad hoc networks based on the topology of clusters previously built. The security of our protocol is strengthened by its clustering criterion which constantly monitors trust relationships and expels malicious nodes out of the multicast session.

Ce travail est dédié à la conception, l’analyse et l’évaluation des performances de nouveaux schémas de codage appropriés aux systèmes de stockage distribué. La première partie de ce travail est consacrée à l’étude des performances des codes spatialement couplés pour les canaux à effacements. Une nouvelle méthode de couplage spatial des ensembles classiques de contrôle de parité à faible densité (LDPC) est proposée. La méthode est inspirée du codage en couches. Les arêtes des ensembles locaux et celles définissant le couplage spatial sont construites séparément. Nous proposons également de saturer le seuil d’un ensemble Root-LDPC par couplage spatial de ses bits de parité dans le but de faire face aux évanouissements quasi-statiques. Le couplage spatial est dans un deuxième temps appliqué à un ensemble Root-LDPC, ayant une double diversité, conçu pour un canal à effacements par blocs à 4 états. Dans la deuxième partie de ce travail, nous considérons les codes produits non-binaires avec des composantes MDS et leur décodage algébrique itératif ligne-colonne sur un canal à effacements. Les effacements indépendants et par blocs sont considérés. Une représentation graphique compacte du code est introduite avec laquelle nous définissions la notion de coloriage à double diversité. Les ensembles d’arrêt sont définis et une caractérisation complète est donnée. La performance des codes produits à composantes MDS, avec et sans coloration, à double diversité est analysée en présence d’effacements indépendants et par blocs. Les résultats numériques montrent aussi une excellente performance en présence d’effacements à probabilité inégale due au coloriage ayant une double diversité. / This work is dedicated to the design, analysis, and the performance evaluation of new coding schemes suitable for distributed storage systems. The first part is devoted to spatially coupled codes for erasure channels. A new method of spatial coupling for low-density parity-check ensembles is proposed. The method is inspired from overlapped layered coding. Edges of local ensembles and those defining the spatial coupling are separately built. We also propose to saturate the whole Root-LDPC boundary via spatial coupling of its parity bits to cope with quasi-static fading. Then, spatial coupling is applied on a Root-LDPC ensemble with double diversity designed for a channel with 4 block-erasure states. In the second part of this work, we consider non-binary product codes with MDS components and their iterative row-column algebraic decoding on the erasure channel. Both independent and block erasures are considered. A compact graph representation is introduced on which we define double-diversity edge colorings via the rootcheck concept. Stopping sets are defined and a full characterization is given in the context of MDS components. A differential evolution edge coloring algorithm that produces colorings with a large population of minimal rootcheck order symbols is presented. The performance of MDS-based product codes with and without double-diversity coloring is analyzed in presence of both block and independent erasures. Furthermore, numerical results show excellent performance in presence of unequal erasure probability due to double-diversity colorings.