3 citations · 7 across the 10 of their papers we have counts for
3 papers · 2 filters
Parameterized Complexities of Dominating and Independent Set Reconfiguration
Hans L. Bodlaender, Carla Groenland, Céline M. F. Swennenhuis
We settle the parameterized complexities of several variants of independent set reconfiguration and dominating set reconfiguration, parameterized by the number of tokens. We show t…
Isolation schemes for problems on decomposable graphs
Jesper Nederlof, Michał Pilipczuk, Céline M. F. Swennenhuis +1
The Isolation Lemma of Mulmuley, Vazirani and Vazirani [Combinatorica'87] provides a self-reduction scheme that allows one to assume that a given instance of a problem has a unique…
Parameterized Problems Complete for Nondeterministic FPT time and Logarithmic Space
Hans L. Bodlaender, Carla Groenland, Jesper Nederlof +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 and space (…