Evènement pour le groupe Combinatoire Énumérative et Algébrique


Date 2013-09-20  10:45-11:45
TitreCompression d'arbres 
RésuméIl est classique de compresser des arbres en DAG (graphes acycliques orientés) en identifiant les sommets auxquels le même sous-arbre est attaché. Combien de place a-t-on ainsi gagné, en termes de nombre de sommets ou d'arêtes ? Flajolet, Sipala et Steyaert ont énoncé en 1990 des résultats (hélas sans preuve) sur ces questions. Par exemple, un arbre binaire à n sommets donnerait, en moyenne, un DAG de taille n/sqrt(log n), et cela semble être le cas pour de nombreuses autres familles d'arbres. On expliquera pourquoi ce résultat est vrai, et envisagerons quelques variations sur ce thème. Travail en commun avec Markus Lohrey et Eric Noeth, Leipzig.  
Lieu076 
OrateurMireille Bousquet-Mélou 



Aucun document lié à cet événement.

Retour
Retour à l'index