Parameterized Complexity, by Serge Gaspers
Jérémy Barbay 8 Abr 201008/04/10 a las 16:47 hrs.2010-04-08 16:47:08
**** Parameterized Complexity, by Serge Gaspers
[2010-04-20 Tue 14:30-16:00]
I. Introduction to Parameterized Complexity
a. Motivation
b. Examples of parameters
c. Complexity classes (P \subseteq FPT \subseteq W[1] \subseteq W[2])
II. FPT Algorithms
a. Vertex Cover: definition and example
b. General Argument by Graph Minors
c. Algorithms for Vertex Cover
III. W-Hardness reductions
a. Definition of classical vs. parameterized hardness reduction
b. Induced Biclique: definition and example
c. Induced Biclique is W[1]-hard
[2010-04-20 Tue 14:30-16:00]
I. Introduction to Parameterized Complexity
a. Motivation
b. Examples of parameters
c. Complexity classes (P \subseteq FPT \subseteq W[1] \subseteq W[2])
II. FPT Algorithms
a. Vertex Cover: definition and example
b. General Argument by Graph Minors
c. Algorithms for Vertex Cover
III. W-Hardness reductions
a. Definition of classical vs. parameterized hardness reduction
b. Induced Biclique: definition and example
c. Induced Biclique is W[1]-hard
| Última Modificación | 20 Abr 201020/04/10 a las 11:24 hrs.2010-04-20 11:24:20 |
|---|---|
| Vistas Únicas | 0 |
| Compartir | |
| Comentarios |
|
