2 citations · 4 across the 4 of their papers we have counts for
7 papers
Exact antichain saturation numbers via a generalisation of a result of Lehman-Ron
Paul Bastide, Carla Groenland, Hugo Jacob +1
For given positive integers and , a family of subsets of is -antichain saturated if it does not contain an antichain of size , but adding…
List Colouring Trees in Logarithmic Space
Hans L. Bodlaender, Carla Groenland, Hugo Jacob
We show that List Colouring can be solved on -vertex trees by a deterministic Turing machine using bits on the worktape. Given an -vertex graph and a li…
On the parameterized complexity of computing tree-partitions
Hans L. Bodlaender, Carla Groenland, Hugo Jacob
We study the parameterized complexity of computing the tree-partition-width, a graph parameter equivalent to treewidth on graphs of bounded maximum degree. On one hand, we can obta…
On the Complexity of Problems on Tree-structured Graphs
Hans L. Bodlaender, Carla Groenland, Hugo Jacob +2
In this paper, we introduce a new class of parameterized problems, which we call XALP: the class of all parameterized problems that can be solved in time and $f(k)\l…
Bounding twin-width for bounded-treewidth graphs, planar graphs, and bipartite graphs
Hugo Jacob, Marcin Pilipczuk
Twin-width is a newly introduced graph width parameter that aims at generalizing a wide range of "nicely structured" graph classes. In this work, we focus on obtaining good bounds…
XNLP-completeness for Parameterized Problems on Graphs with a Linear Structure
Hans L. Bodlaender, Carla Groenland, Hugo Jacob +2
In this paper, we showcase the class XNLP as a natural place for many hard problems parameterized by linear width measures. This strengthens existing -hardness proofs for the…