Laboratoire de Mathématiques Raphaël Salem

UMR 6085 CNRS - Université de Rouen Normandie

Résumé : Dans cet exposé, nous décrivons une technique de construction et exploration couplées, pour plusieurs algorithmes séquentiels sur de grands graphes aléatoires.
Le modèle considéré est le modèle de configuration, qui permet de générer un graphe uniformément au hasard, suivant une distribution de degrés donnée. Ce modèle, populaire notamment pour modéliser les réseaux sociaux et épidémiologiques, permet en outre une construction markovienne que nous pouvons coupler avec un algorithme d'exploration sur le graphe. Ceci nous permet d'obtenir une convergence en grand graphe vers la solution d'une EDO et par-là même, une approximation de certaines caractéristiques de l'algorithme considéré. Nous donnons deux exemples: l'algorithme de parking pour la construction d'une famille indépendante maximale, et des algorithmes de couplage 'locaux'. Travaux joints avec Paola Bermolen et Matthieu Jonckheere / Mohamed Habib Diallo Aoudi et Vincent Robin.