1 citations · 1 across the 3 of their papers we have counts for
3 papers
cs.DS2025★ 1 cited
A Parameterized Complexity Analysis of Bounded Height Depth-first Search Trees
Lars Jaffke, Paloma T. de Lima, Wojciech Nadara +1
Computing bounded depth decompositions is a bottleneck in many applications of the treedepth parameter. The fastest known algorithm, which is due to Reidl, Rossmanith, Sánchez Vill…
cs.CC2023
Treewidth is NP-Complete on Cubic Graphs (and related results)
Hans L. Bodlaender, Édouard Bonnet, Lars Jaffke +6
In this paper, we give a very simple proof that Treewidth is NP-complete; this proof also shows NP-completeness on the class of co-bipartite graphs. We then improve the result by B…
math.CO2022
On the maximum number of edges in planar graphs of bounded degree and matching number
Lars Jaffke, Paloma T. Lima
We determine the maximum number of edges that a planar graph can have as a function of its maximum degree and matching number.