Ismael Belghiti (ENS, Paris)

Étant données deux permutations de [1, n ], un intervalle commun est un sous-ensemble de [1, n ] qui apparaît de façon contiguë dans chacune des deux permutations : par exemple {1,2,4} est un intervalle commun aux permutations P 1 = (3,4,2,1,5,6) et P 2 = (6,5,1,4,2,3).

Bien que l’ensemble des intervalles communs de deux permutations puisse être de taille quadratique, il existe une représentation linéaire de celui-ci.

Nous présenterons un algorithme efficace pour calculer une telle représentation et montrerons comment étendre les concepts présentés à d’autres problèmes. Notamment, nous montrerons comment calculer, pour un arbre sur l’ensemble de sommets [1, n ], la famille des intervalles qui correspondent à un sous-arbre.