Kernelisation, by Serge Gaspers
Jérémy Barbay 8 Abr 201008/04/10 a las 16:47 hrs.2010-04-08 16:47:08
Kernelisation, by Serge Gaspers
[2010-04-22 Thu 14:30-16:00]
I. Recall
a. FPT
b. W[1]
c. Vertex Cover
II. Introduction to Kernelization
a. Kernelization Algorithm: definition
b. Example: a O(k^2) kernel for Vertex Cover
c. A problem is FPT iff it has a kernel
III. Crown Decomposition
a. Crown Decomposition: definition and example
b. Crown Reduction for Vertex Cover
c. Vertex Cover has a 4k kernel
[2010-04-22 Thu 14:30-16:00]
I. Recall
a. FPT
b. W[1]
c. Vertex Cover
II. Introduction to Kernelization
a. Kernelization Algorithm: definition
b. Example: a O(k^2) kernel for Vertex Cover
c. A problem is FPT iff it has a kernel
III. Crown Decomposition
a. Crown Decomposition: definition and example
b. Crown Reduction for Vertex Cover
c. Vertex Cover has a 4k kernel
| Última Modificación | 20 Abr 201020/04/10 a las 11:25 hrs.2010-04-20 11:25:20 |
|---|---|
| Vistas Únicas | 0 |
| Compartir | |
| Comentarios |
|
