|
Evènement pour le groupe GT Graphes et Applications
Date | 2011-12-09 14:00-15:00 |
Titre | Le 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.
|
Lieu | Salle 4, Bât A29 |
Orateur | Frédéric Mazoit |
Url | LaBRI |
Aucun document lié à cet événement. RetourRetour à l'index
| |