Evènement pour le groupe GT Graphes et Applications

Date 2011-03-04  14:00-15:00
TitreAn algorithmic decomposition of claw-free graphs leading to an O (n^3)-algorithm for the weighted stable set problem  
RésuméWe propose an algorithm for solving the maximum weighted stable set problem on claw-free graphs that runs in $O(n^3)$-time, drastically improving the previous best known complexity bound. This algorithm is based on a novel decomposition theorem for claw-free graphs, which is also introduced in the present paper. Despite being weaker than the well-known structure result for claw-free graphs given by Chudnovsky and Seymour, our decomposition theorem is, on the other hand, algorithmic, i.e. it is coupled with an $O(n^3)-$time procedure that actually produces the decomposition. We also believe that our algorithmic decomposition result is interesting on its own and might be also useful to solve other kind of problems on claw-free graphs. 
LieuSalle 178 
OrateurGautier Stauffer 

Aucun document lié à cet événement.

Retour à l'index