CS
C.M.F. Swennenhuis
info
Please Note
<p>This page displays the records of the person named above and is not linked to a unique person identifier. This record may need to be merged to a profile.</p>
2 records found
1
Let XNLP be the class of parameterized problems such that an instance of size n with parameter k can be solved nondeterministically in time f(k)nO(1) and space f(k)log(n) (for some computable function f). We give a wide variety of XNLP-complete problems, such as LIST COLORING and PRECOLORING EXTENSION with pathwidth as parameter, SCHEDULING OF JOBS WITH PRECEDENCE CONSTRAINTS, with both number of machines and partial order width as parameter, BANDWIDTH and variants of WEIGHTED CNF-SATISFIABILITY. In particular, this implies that all these problems are W[t]-hard for all t.
...
Let XNLP be the class of parameterized problems such that an instance of size n with parameter k can be solved nondeterministically in time f(k)nO(1) and space f(k)log(n) (for some computable function f). We give a wide variety of XNLP-complete problems, such as LIST COLORING and PRECOLORING EXTENSION with pathwidth as parameter, SCHEDULING OF JOBS WITH PRECEDENCE CONSTRAINTS, with both number of machines and partial order width as parameter, BANDWIDTH and variants of WEIGHTED CNF-SATISFIABILITY. In particular, this implies that all these problems are W[t]-hard for all t.