From the 1 of 10 linked papers with an AI index.
4 papers · 1 filter
The Parameterized Complexity of Problems on Outer k-Planar Graphs
Xiaobin Ren, Hans L. Bodlaender
The paper investigates the parameterized complexity of many classic graph problems on outer k‑planar graphs, showing that most become fixed‑parameter tractable when k is the parame…
The Parameterized Complexity of Scheduling with Precedence Delays: Shuffle Product and Directed Bandwidth
Hans L. Bodlaender, Maher Mallem
In this paper, we study the parameterized complexity of several variants of scheduling with precedence constraints between jobs. Namely, we consider the single machine setting with…
On Stable Cutsets in General and Minimum Degree Constrained Graphs
Mats Vroon, Hans L. Bodlaender
A stable cutset is a set of vertices of a connected graph, that is pairwise non-adjacent and when deleting , the graph becomes disconnected. Determining the existence of a s…
Finding sparse induced subgraphs on graphs of bounded induced matching treewidth
Hans L. Bodlaender, Fedor V. Fomin, Tuukka Korhonen
The induced matching width of a tree decomposition of a graph is the cardinality of a largest induced matching of , such that there exists a bag that intersects every ed…