Parameterized Complexity and Subexponential-Time Computability
Conference Paper
Overview
Research
Identity
Additional Document Info
Other
View All
Overview
abstract
Since its inception in the 1990's, parameterized complexity has established itself as one of the major research areas in theoretical computer science. Parameterized and kernelization algorithms have proved to be very useful for solving important problems in various domains of science and technology. Moreover, parameterized complexity has shown deep connections to traditional areas of theoretical computer science, such as structural complexity theory and approximation algorithms. In this paper, we discuss some of the recent results pertaining to the relation between parameterized complexity and subexponential-time computability. We focus our attention on satisfiability problems because they play a key role in the definition of both parameterized complexity and structural complexity classes, and because they model numerous important problems in computer science. 2012 Springer-Verlag Berlin Heidelberg.
name of conference
The Multivariate Algorithmic Revolution and Beyond - Essays Dedicated to Michael R. Fellows on the Occasion of His 60th Birthday