Evènement pour le groupe GT Graphes et Applications


Date 2011-12-09  14:00-15:00
TitreLe théorème du sommet redondant pour les graphes sur les surfaces 
RésuméÉtant donnés k couples (s1, t1), ..., (sk, tk) de sommets dans un graphes, le problème des k chemins disjoint (k-DDP) demande s'il existe k chemins disjoints dont les extrémités sont les couples (si, ti). Robertson et Seymour ont donné un algorithme qui fonctionne en temps O(n^3) pour résoudre ce problème. Dans certains cas, l'algorithme donne une réponse directe, sinon, il identifie un ''sommet redondant'' dont la suppression ne change pas la réponse au problème. Malheureusement, cet algorithme fait intervenir des constantes dont l'existence n'est montré que de façon existentielle et même si Robertson et Seymour ont affirmé qu'il était possible de rendre effectif leurs preuves, ce travail n'avait pas encore été fini. Dans cet exposé, je présenterai un travail en collaboration avec Geelen, Huynh et Richter dans lequel nous terminons ce travail en donnant une preuve effective du théorème du sommet redondant pour les graphes sur les surfaces.  
LieuSalle 4, Bât A29 
OrateurFrédéric Mazoit 
UrlLaBRI 



Aucun document lié à cet événement.

Retour
Retour à l'index