8 citations · 66 across the 52 of their papers we have counts for
8 papers · 1 filter
Lossy kernels for connected distance- domination on nowhere dense graph classes
Sebastian Siebertz
For , an -approximate bi-kernel is a polynomial-time algorithm that takes as input an instance of a problem and outputs an i…
Algorithmic Properties of Sparse Digraphs
Stephan Kreutzer, Patrice Ossona de Mendez, Roman Rabinovich +1
The notions of bounded expansion and nowhere denseness have been applied very successfully in algorithmic graph theory. We study the corresponding notions of directed bounded expan…
Reconfiguration on nowhere dense graph classes
Sebastian Siebertz
Let be a vertex subset problem on graphs. In a reconfiguration variant of we are given a graph and two feasible solutions o…
Distributed Dominating Set Approximations beyond Planar Graphs
Saeed Akhoondian Amiri, Stefan Schmid, Sebastian Siebertz
The Minimum Dominating Set (MDS) problem is one of the most fundamental and challenging problems in distributed computing. While it is well-known that minimum dominating sets canno…
On the number of types in sparse graphs
Michał Pilipczuk, Sebastian Siebertz, Szymon Toruńczyk
We prove that for every class of graphs which is nowhere dense, as defined by Nesetril and Ossona de Mendez, and for every first order formula , whe…
On low rank-width colorings
O-joung Kwon, Michał Pilipczuk, Sebastian Siebertz
We introduce the concept of low rank-width colorings, generalising the notion of low tree-depth colorings introduced by Nešetřil and Ossona de Mendez in [Grad and classes with boun…