Les codes identifiants ont été introduits par Karpovsky, Chakrabarty et Levitin en 1998 pour modéliser un problème de détection de défaillances dans les réseaux. Depuis, ces codes ont trouvé des applications dans des domaines divers tels que la surveillance de bâtiments par des réseaux de capteurs ou l’analyse de structures secondaires d’ARN.

Mes travaux se situent dans le champ des mathématiques discrètes. Ils portent sur l’étude des codes identifiants dans les graphes. La question générale consistant à déterminer la cardinalité minimum d’un tel code est un problème NP-difficile. Les questions abordées dans cette habilitation concernent :

• l’étude de structures régulières (grilles, puissances de cycles, hypercubes, produits de cliques, graphes de Sierpinski) ;
• les aspects algorithmiques (approximabilité du problème, algorithmes dédiés pour des classes particulières de graphes) ;
• les considérations structurelles (bornes générales, graphes extrémaux, construction de code)
• les codes adaptatifs.

Après une introduction au domaine et une discussion sur la dynamique actuelle de ce thème de recherche, je présenterai quelques-unes de mes contributions dans chacun des thèmes ci-dessus. En conclusion, je discuterai des sujets de recherche émergents liés à ces codes, et présenterai mes projets de recherche.