Add to ORKGIn this short survey, a number of old and new notions from parameterized complexity are discussed. We start with looking at the W-hierarchy, including the classes W[1], W[2], W[P]. Then, a recent development where problems are shown to be complete for simultaneously non-deterministic time of the form f(k) nc and space of the form f(k) log n, is discussed. Some consequences and other notions are briefly explored
AbstractWe describe parameterized complexity classes by means of classical complexity theory and des...
A parameterized computational problem is a set of pairs 〈x, k〉, where k is a distinguished item call...
The central conjecture of parameterized complexity states that FPT !=W[1], and is generally regarded...
In this short survey, a number of old and new notions from parameterized complexity are discussed. W...
We study the theory and techniques developed in the research of parameterized intractability, emphas...
We give machine characterizations of most parameterized complexity classes, in particular, of W[P], ...
Let XNLP be the class of parameterized prob-lems such that an instance of size n with parameter k ca...
The parameterized complexity of a problem is generally considered “settled ” once it has been shown ...
Let XNLP be the class of parameterized problems such that an instance of size $n$ with parameter $k$...
AbstractFixed-parameter intractability of optimization problems in NP is studied based on computatio...
AbstractMotivated by recent results showing that there are natural parameterized problems that are f...
We extend the reach of fixed-parameter analysis by introducing classes of parameterized sets defined...
AbstractFor many fixed-parameter problems that are trivially solvable in polynomial-time, such as k-...
AbstractWe study a refined framework of parameterized complexity theory where the parameter dependen...
Asking which sets are fixed-parameter tractable for a given parameterization constitutes much of the...
AbstractWe describe parameterized complexity classes by means of classical complexity theory and des...
A parameterized computational problem is a set of pairs 〈x, k〉, where k is a distinguished item call...
The central conjecture of parameterized complexity states that FPT !=W[1], and is generally regarded...
In this short survey, a number of old and new notions from parameterized complexity are discussed. W...
We study the theory and techniques developed in the research of parameterized intractability, emphas...
We give machine characterizations of most parameterized complexity classes, in particular, of W[P], ...
Let XNLP be the class of parameterized prob-lems such that an instance of size n with parameter k ca...
The parameterized complexity of a problem is generally considered “settled ” once it has been shown ...
Let XNLP be the class of parameterized problems such that an instance of size $n$ with parameter $k$...
AbstractFixed-parameter intractability of optimization problems in NP is studied based on computatio...
AbstractMotivated by recent results showing that there are natural parameterized problems that are f...
We extend the reach of fixed-parameter analysis by introducing classes of parameterized sets defined...
AbstractFor many fixed-parameter problems that are trivially solvable in polynomial-time, such as k-...
AbstractWe study a refined framework of parameterized complexity theory where the parameter dependen...
Asking which sets are fixed-parameter tractable for a given parameterization constitutes much of the...
AbstractWe describe parameterized complexity classes by means of classical complexity theory and des...
A parameterized computational problem is a set of pairs 〈x, k〉, where k is a distinguished item call...
The central conjecture of parameterized complexity states that FPT !=W[1], and is generally regarded...