Showing cs.DMShow all
3 papers · 1 filter
cs.DM2022
Parameterized Complexity of Binary CSP: Vertex Cover, Treedepth, and Related Parameters
Hans L. Bodlaender, Carla Groenland, Michał Pilipczuk
We investigate the parameterized complexity of Binary CSP parameterized by the vertex cover number and the treedepth of the constraint graph, as well as by a selection of related m…
cs.DM2022
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…
cs.DM2022
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…