Robustesse

Swan Dubois (Sorbonne Université - LIP 6) fera un séminaire le jeudi 9 mars 2023 en salle 301 à 14h.

Résumé

Dans cet exposé, nous introduirons la notion de propriété (ou structure) robuste dans un graphe comme un cas particulier de propriété (ou structure) héréditaire sur l'ensemble des sous-graphes connexes du graphe. Nous montrerons que cette propriété de robustesse trouve une application naturelle dans le cadre de l'algorithmique répartie sur les systèmes dynamiques.
Nous étudierons ensuite le cas de l'ensemble indépendant maximal robuste avec notamment un algorithme polynomial de reconnaissance de cette structure. Nous conclurons en présentant succinctement des travaux en cours sur cette propriété de robustesse.