Affinage de partition chez les graphes.

L'objectif de ce sujet est de présenter le paradigme d'affinage de partition en algorithmique avec des applications aux graphes. On pourra travailler à partir de la thèse de Christophe Paul (depuis le chapitre 4, page 87) :

• Manuscript de thèse de C. Paul

On pourra par exemple illustrer ce paradigme avec le calcul de sommets jumeaux, le tri lexicographique de chaines de caractères (meme si ce n'est pas tout à fait des graphes), le calcul de parcours Lex-BFS ou d'autres exemples tirés du manuscript ou d'articles que vous pouvez trouver utilisant cette technique.