Je fais partie de l'équipe de Combinatoire et Algorithmique du LaBRI en participant aux activités des groupes:
Mes principaux thèmes de recherche portent sur :
Le problème général du routage dans les réseaux distribués arbitraires et les machines parallèles consiste à développer des méthodes pour acheminer des messages d'un noeud à un autre. Lorsque les réseaux sont grands, il devient nécessaire de limiter la quantité d'informations nécessaire à chaque routeur tout en préservant un acheminement rapide des messages.
L'approche que nous proposons montre que la représentation d'un réseau "aide" au routage car nous construisons des tables de routage, contenu dans chaque routeur, dont la taille est paramétré par une caractéristique topologique des graphes sous-jacents, le genre de la surface de plongement (cf. Publications 3,9,11).
Recherche d'informations par agents mobiles dans un réseau incertain
L'explosion d'informations dans les réseaux de type Internet ont favorisé l'idée d'avoir des ``explorateurs personnels'' recherchant les informations dans le Web. Ces explorateurs sont des programmes mobiles qui parcourent le réseau et ont la capacité de réaliser certaines tâches prédéfinies. Par exemple, le rappel automatique de rendez-vous, la composition périodique de numéros de téléphone, la recherche de noeuds defaillants, la quête d'informations, ...
Nous nous sommes intéressées aux problèmes de recherche d'informations dans un réseau en présence de ``menteurs''. L'objectif est de proposer un agent mobile qui parcourt les liens du réseau pour repérer une information ou un service (que j'appelle objet par la suite). Le modèle considéré est le suivant: la localisation et l'adresse de l'objet sont inconnues initialement mais des informations sur la direction à suivre peuvent être obtenues en interrogeant les noeuds du réseau. Chaque noeud possède une base de données indiquant un ou plusieurs liens à suivre pour atteindre l'objet avec le plus court chemin. Cependant, certains noeuds peuvent être menteurs indiquant une mauvaise route, simplement parce qu'ils ne sont plus à jour ou défaillants. Les menteurs sont inconnus de l'agent mobile et ce dernier doit prendre une décision de déplacement même si les indications données sont mauvaises. Nous nous sommes interessés à différentes variations de ce modèle pour proposer des algorithmes déterministes et probabilistes pour la recherche d'informations dans un réseau distribué avec un nombre borné de menteurs. Nous avons considéré différentes topologies: graphe complet, l'anneau, le tore, l'hypercube, les arbres afin de développer des agents mobiles spécifiques (cf. Publications 1,2,6,7).
Une carte est une représentation d'un graphe sur une surface. Cet objet intervient dans bien des domaines et correspond à une formalisation d'objets apparemment différents : d'un point de vue concret, il peut s'agir de carte géographique, circuit VLSI, structures d'ADN, ... mais aussi d'objets mathématiques tels que des groupes de permutations, courbes représentatives de fonctions dans la théorie des dessins d'enfants. Les deux thèmes suivants sont traités dans ma thèse intitulé:
Cartes, constellations et groupes: questions algorithmiques
Ma thèse en un seul bloc - 813 Kb -: Cartes, constellations et groupes: questions algorithmiques (211 pages)
En la découpant en 6 parties:Algorithmes de dessins de graphes et de cartes
Dans de nombreuses applications de représentation de données, nous considérons la structure ou la topologie sous-jacente modéliser par un graphe. Le problème du dessin de graphes ou de cartes consiste à placer de manière automatique les sommets d'un graphe donné et de décrire la forme de chaque arête en respectant des contraintes d'esthétisme. Par exemple, représenter un graphe planaire sans intersection d'arêtes.
J'ai proposé des algorithmes de représentations de cartes avec des arêtes courbes, modélisés par des splines (cf. Publication 12).
Le codage combinatoire de la carte peut se faire à l'aide de permutations. Nous associons à une carte son groupe cartographique, le groupe de permutations engendré par les deux permutations codant la carte. Je me suis intéressé à une généralisation de l'hypercarte, nommée constellation, codée par un k-uplet de permutations. La théorie des dessins d'enfants du à Grothendieck est une théorie mathématique qui mèle différents domaines : la théorie des cartes, théorie des groupes, théorie des surfaces de Riemann, théorie des nombres, ...
Ma contribution a consisté à développer des algorithmes de manipulation de cartes et groupes cartographiques pour étudier des relations entre la géométrie des cartes et des propriétés algébriques de groupes (cf. Publications 5,8,10).
Algorithmes de convexification de polygones
L'origine de ce travail vient d'une question simple mais peut mener à de nombreuses applications: prenons un polygone, peut-on le rendre convexe en préservant les pentes et les longueurs de ses cotês à l'aide d'opérations élémentaires ? D'un point de vue pratique, les réponses à cette question peuvent mener à des réponses sur l'amélioration éventuelle d'une représentation graphique de graphes, de réseaux ou sur des déplacements contraints de robots dans un environnement. Il existe aussi des relations entre cette question et des questions posées en physique statistique où les modèles de percolation sont étudiés à travers leurs représentations nommées ``animaux'' (polygônes à trou) ou sur la représentation de polymères.
En considérant une opération de symétrie, appliquée à une partie de l'enveloppe convexe, nous montrons que tout polygone est "convexifiable" en un nombre linéaire d'opérations pour un nombre de pentes fixé (cf. Publication 4)..