Résumé : Un graphe ordonné est un graphe dans lequel les sommets sont ordonnés de
1 à n. Un motif est un graphe ordonné qui contient deux types d’arêtes :
les arêtes obligatoires et les arêtes interdites. Étant donné un motif,
la question que l’on s’est posée avec Michel Habib, Laurent Feuilloley
et Guillaume Ducoffe est celle de trouver un algorithme rapide qui
détecte si un motif apparait ou non dans un graphe ordonné donné en
entré. Naïvement, si le motif contient k sommets, cela se fait en temps
O(n^k). Cependant, on a pu montrer qu’il existait des classes de motifs
pour lesquels l’exposant ne dépend pas de la taille du motif. De plus,
nous avons introduit un nouveau paramètre p qui permet de décomposer les
motifs, et tel que tout motif de paramètre p puisse être détecté en
temps O(n^(cp)), où c est une constante entre 1 et 2.
Bio : François Pitois est un doctorant en 3ème année de thèse dans l’équipe
CombNet du LIB et dans l’équipe Graphes, Algorithmes et Applications du
LIRIS, sous la direction d’Olivier Togni et la codirection de Hamida
Seba et Mohammed Haddad. Il travaille sur la recherche de motifs et de
régularité dans les graphes.