Evènement pour le groupe GT Graphes et Applications


Date 2012-05-15  11:00-12:00
TitreChemins disjoints avec congestion dans les graphes à mineur exclu 
RésuméNous étudions le problème de trouver un nombre maximum de chemins disjoints dans des classes de graphes fermées par mineur. En général, ce problème est très difficile à approximer, même dans des classes très simples comme les graphes planaires, avec des ratios d'inapproximabilité en $Omega(sqrt{n})$ ou plus. Pour contourner cette difficulté, plusieurs travaux autorisent l'utilisation de congestion: sous congestion $c$, on autorise $c$ chemins à utiliser la même arête. Chuzhoy a montré en 2011 qu'en permettant une congestion constante, il existe une algorithme de ratio polylogarithmique. Si nous cherchons plutôt des algorithmes ayant des ratios d'approximations constants, Chekuri, Khanna et Shepherd ont pu trouver un algorithme avec ratio d'approximation constant et congestion 2, dans le cas des graphes planaires. Nous souhaitons généraliser ce résultat, et nous prouvons que pour les graphes à largeur d'arbre bornée, et pour les graphes plongeables dans une surface fixée, il existe des algorithmes avec ratio et congestion constants. Ces deux types de classes de graphes étant fermées par mineur, nous conjecturons que toute classe de graphes à mineur exclu admet de tels algorithmes.  
LieuAmphi du LaBRI 
OrateurGuyslain Naves 
UrlUniversité de Montréal 



Aucun document lié à cet événement.

Retour
Retour à l'index