Journée-séminaire de combinatoire

(équipe CALIN du LIPN, université Paris-Nord, Villetaneuse)

Le 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.


Dernière modification : Tuesday 08 January 2019 Valid HTML 4.01! Valid CSS! Contact : Cyril.Banderier at lipn.univ-paris13.fr