Michel Habib (LIAFA, Paris)

Les parcours de graphes constituent un outil essentiel de l’algorithmique de graphes. En outre leur simplicité d’implémentation permet de les utiliser sur des très grands graphes.

Après quelques rappels historiques, je présenterai plusieurs résultats récents:

  • des nouvelles caractérisations des ordres de parcours classiques
  • la définition d’un nouveau parcours en profondeur lexicographique aux propriétés remarquables
  • l’usage de suites parcours dépendants. Dans cette nouvelle approche algorithmique un parcours peut utiliser des informations du parcours précédent en particulier l’ordre de visite des sommets. Des premières applications seront décrites: pour le calcul du diamètre de très grands graphes ainsi que pour la reconnaissance des graphes de cocomparabilité.

En fait comme on peut le deviner dans le dernier item, la question centrale posée est :

Que peut-on apprendre de la structure d’un graphe en exécutant une série de parcours de graphes?

En conclusion je formaliserai cette question et proposerai des nouvelles applications telles que le clustering de graphes ou la détection de communautés dans les réseaux sociaux.