Séminaires


Retour à la liste de tous les séminaires


À la recherche de longs chemins simples dans les graphes d'Erdös-Rényi

Le : 11/06/2018 11h00
Par : Laurent Ménard (Paris Ouest)
Lieu : i103
Lien web :
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 les recherches en profondeur convergent vers une limite déterministe explicite. Cela exhibe entre autres des chemins simples du graphe de longueur linéaire en N. Travaux en commun avec N. Enriquez, G. Faraud et N. Noiry (Modal'X, Paris Nanterre)