Parameterized Complexity and Subexponential-Time Computability Conference Paper uri icon

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

published proceedings

  • Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

author list (cited authors)

  • Chen, J., & Kanj, I. A.

citation count

  • 5

complete list of authors

  • Chen, Jianer||Kanj, Iyad A

publication date

  • July 2012