MASCOTTE no longer exists => visit the new project-team
Seminaire MASCOTTEProtrusions in graphs and their applications
par Fedor Fomin
| Date : | 12/04/11 | | Time : | 10h30 | | Location : | Galois Coriolis |
Protrusions were introduced by Bodlaender et al. as a tool for obtaining kernelization meta-theorems. Loosely speaking, if a parametrized problem can be expressed in a certain logic, then a sufficiently large protrusion can be replaced by a smaller ''equivalent" one . Protrusions appear to be a handy tool for obtaining kernelization and approximation algorithms. In this talk we discuss combinatorial properties of graphs implying existence of large protrusions and give a number of algorithmic applications of protrusions.
Page des séminaires
| 
