Showing cs.DMShow all
3 papers · 1 filter
cs.DM2026
Weighted Treedepth is NP-complete on Graphs of Bounded Degree
Jona Dirks, Nicole Schirrmacher, Sebastian Siebertz +1
A treedepth decomposition of an undirected graph is a rooted forest on the vertex set of such that every edge is in ancestor-descendant relationship in …
cs.DM2025
Lower bounds for dominating set reconfiguration on sparse (directed) graphs
Jona Dirks, Alexandre Vigny
In a graph, a vertex dominates itself and its neighbors, and a dominating set is a set of vertices that together dominate the entire graph. Given a graph and two dominating sets of…
cs.DM2025
Token Sliding Reconfiguration on DAGs
Jona Dirks, Alexandre Vigny
Given a graph and two independent sets of same size, the Independent Set Reconfiguration Problem under token sliding ask whether one can, in a step by step manner, transform th…