Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Thursday, April 18, 2013, 12:15 pm
Duration: 30 minutes
Location: OAT S15/S16/S17
Speaker: Yoichi Iwata (University of Tokyo)
In the area of parameterized complexity, to cope with NP-Hard problems, we introduce a parameter k besides the input size n, and we aim to design algorithms (called FPT algorithms) that run in O(f(k)n^d) time for some function f(k) and constant d. Though FPT algorithms have been successfully designed for many problems, typically they are not sufficiently fast because of huge f(k) and d. In this talk, we give FPT algorithms with small f(k) and d for many important problems including Odd Cycle Transversal and Almost 2-SAT. More specifically, we show that we can choose f(k) as a single exponential and d as one, that is, linear in the input size. To the best of our knowledge, for these problems, our algorithms achieve linear time complexity for the first time.
Automatic MiSe System Software Version 1.4803M | admin login