Tutorial
Title： On Fixed-Parameter and Exact Algorithms
Speaker：Rolf Niedermeier, Friedrich-Schiller-Universitaet Jena,Germany
Peter Rossmanith, RWTH Aachen University, Aachen, Germany
Date：2008/09/04～2008/09/05
Venue：IIS, Academia Sinica, Taipei.
Location
Abstract
The tutorial surveys main techniques and results in the development of exactand fixed-parameter algorithms. We concentrate mainly on the algorithmic(and less on the complexity-theoretic) side, exhibiting techniques such assearch trees, polynomial-time data reduction and kernelization, iterativecompression, color-coding etc. The problems we discuss occur in variousdomains, ranging from computational biology to computational social choice.
Registration!!
Program
Sep. 4, 2008 | 09:00
~
10:15 | Introduction to Exact and Parameterized Algorithm | | 10:15
~
10:45 | Coffee Break | | 10:45
~
12:00 | Search Trees | | 12:00
~
14:00 | Break | | 14:00
~
15:15 | Problem Kernels and Data Reduction | | 15:15
~
15:45 | Coffee Break | | 15:45
~
17:00 | Randomized Design Techniques | Sep. 5, 2008 |
09:00
~
10:15 |
Tree-Width Based Approaches |
| 10:15
~
10:45 |
Coffee Break | |
10:45
~
12:00 |
Iterative Compression | |
12:00
~
14:00 |
Break | |
14:00
~
15:15 |
Other Advanced Techniques | |
15:15
~
15:45 |
Coffee Break | |
15:45
~
17:00 |
Parameterized Hardness | |
