Construction séquentielle d'arbre couvrant minimal

schedule le lundi 20 mai 2019 de 17h00 à 18h00

Organisé par : O. Safsafi, F. Coppini, B. Dembin

Intervenant : SAFSAFI Othmane (LPSM)
Lieu : Sophie Germain, salle 1016, P7

Sujet : Construction séquentielle d'arbre couvrant minimal

Résumé :

Etant donné un graphe complet, on attribue des poids aléatoires indépendants et identiquement distribués à ses arêtes, on se propose ensuite de construire l'arbre couvrant de poids minimal de ce graphe. Sauf qu'au lieu de regarder le graphe dans son ensemble, on se propose de ne voir qu'une partie du graphe à chaque instant et de faire les changement qu'on veut sur cette partie. 

La question qu'on se pose alors est : 
Dans quels conditions peut-on retrouver le vrai arbre couvrant minimal en faisant des changements locaux sur le graphe ?

Cette problématique est très récente, dans cet exposé nous allons expliquer le contexte du problème et donner une réponse positive à la question dans un cas particulier, finalement, nous donnerons quelques idées et approches qui pourrait (ou pas) répondre à la question dans un cadre plus général.