Retour à l'index du GREYC

Séminaire Algorithmique

Site du CNRS

Séminaire Algorithmique

Le séminaire a lieu le mardi à 11 h 45 (sauf modification exceptionnelle), au campus Côte de Nacre, bâtiment Sciences 3, salle S3 351, 3ème étage.

Résumé du séminaire du Mardi 28 Janvier 2014

Intervalles communs de deux permutations et généralisations

par 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 P1 = (3,4,2,1,5,6) et P2 = (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.

GREYC
Campus Côte de Nacre, boulevard du Maréchal Juin
BP 5186
14032 Caen Cedex
FAX : +33 (0)2 31 56 73 30
http://www.greyc.fr