From the 1 of 10 linked papers with an AI index.
10 papers
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…
Trade-off between spread and width for tree decompositions
Hans L. Bodlaender, Carla Groenland
We study the trade-off between (average) spread and width in tree decompositions, answering several questions from Wood [arXiv:2509.01140]. The spread of a vertex in a tree dec…
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…
On Equivalent Characterizations of NP in Abstract Models of Computation
Jeremy C. Kirn, Lucas Meijer, Tillmann Miltzow +1
We investigate machine models similar to Turing machines that are augmented by the operations of a first-order structure , and we show that under weak conditions on $\…
Hedonic Seat Arrangement Problems
Hans L. Bodlaender, Tesshu Hanaka, Lars Jaffke +3
In this paper, we study a variant of hedonic games, called \textsc{Seat Arrangement}. The model is defined by a bijection from agents with preferences for each other to vertices in…