8 citations · 66 across the 52 of their papers we have counts for
70 papers
Almost Optimal Constant-Round Approximation of Dominating Set in Graph Classes with Excluded Minors
Saeed Amiri, Sebastian Siebertz
For every fixed proper minor-closed class and every , we give a deterministic LOCAL algorithm that returns a dominating set of size at most $(2a(\mathscr C)+1+ε)γ…
A Logic for Minor-Free Graph Classes: Model Checking, Dependence, and Combinatorial Reconfiguration
Nikolas Mählmann, Patrice {Ossona de Mendez}, Nicole Schirrmacher +4
We introduce \emph{sub-connectivity logic}, denoted by , an extension of first-order logic for graphs with a specified set of admissible edges. Its additional…
On the Parameterized Complexity of Coloring Discovery
Eric Decker, Sebastian Siebertz
Coloring Discovery asks whether a possibly improper initial coloring can be made proper within a prescribed number of allowed changes. We study the parameterized complexity of thre…
Model Checking for Low Monodimensionality Fragments of CMSO on Topological-Minor-Free Graph Classes
Ignasi Sau, Nicole Schirrmacher, Sebastian Siebertz +3
Algorithmic meta-theorems explain the tractability of large classes of computational problems by linking logical expressibility with structural graph properties. While extensions o…
Separating Feasibility and Movement in Solution Discovery: The Case of Path Discovery
Hanno von Bergen, Larissa Fastenau, Enna Gerhard +8
We study solution discovery, where the goal is to obtain a feasible solution to a problem from an initial configuration by a bounded sequence of local moves. In many applications,…
On merge-models
Hector Buffière, Yuquan Lin, Jaroslav Nešet{ř}il +2
Tree-ordered weakly sparse models have recently emerged as a robust framework for representing structures in an ``almost sparse'' way, while allowing the structure to be reconstruc…