4 citations · 9 across the 4 of their papers we have counts for
4 papers
A Hierarchy of Polynomial Kernels
Jouke Witteveen, Ralph Bottesch, Leen Torenvliet
In parameterized algorithmics, the process of kernelization is defined as a polynomial time algorithm that transforms the instance of a given problem to an equivalent instance of a…
Levelable Sets and the Algebraic Structure of Parameterizations
Jouke Witteveen, Leen Torenvliet
Asking which sets are fixed-parameter tractable for a given parameterization constitutes much of the current research in parameterized complexity theory. This approach faces some o…
Nonapproximablity of the Normalized Information Distance
Sebastiaan A. Terwijn, Leen Torenvliet, Paul M. B. Vitanyi
Normalized information distance (NID) uses the theoretical notion of Kolmogorov complexity, which for practical purposes is approximated by the length of the compressed version of…
P-Selectivity, Immunity, and the Power of One Bit
Lane A. Hemaspaandra, Leen Torenvliet
We prove that P-sel, the class of all P-selective sets, is EXP-immune, but is not EXP/1-immune. That is, we prove that some infinite P-selective set has no infinite EXP-time subset…