Salut,
Cet après-midi, 19 février 2019 à 14h00 en B107, Laurent Ménard nous
parlera de : Recherche en profondeur dans les graphes aléatoires
Erdős-Rényi
Résumé : Dans un graphe d'Erdős-Rényi à N sommets et probabilité de
connexion c/N, on démontrera que les arbres couvrants de la composante
géante construits par des algorithmes d'exploration basés sur la
recherche en profondeur convergent vers une limite déterministe
explicite. Cela exhibe entre autres des chemins simples, éventuellement
induits, du graphe de longueur linéaire en N. Si le temps le permet
j'évoquerai ensuite le cas des graphes construits par modèle de
configuration. Ces résultats sont issus de collaborations avec Gabriel
Faraud, Nathanaël Enriquez et Nathan Noiry.
À tout de suite,
Thierry
