8 citations · 66 across the 52 of their papers we have counts for
5 papers · 1 filter
Constant round distributed domination on graph classes with bounded expansion
Simeon Kublenz, Sebastian Siebertz, Alexandre Vigny
We show that the dominating set problem admits a constant factor approximation in a constant number of rounds in the LOCAL model of distributed computing on graph classes with boun…
Structural properties of the first-order transduction quasiorder
Jaroslav Nesetril, Patrice Ossona de Mendez, Sebastian Siebertz
Logical transductions provide a very useful tool to encode classes of structures inside other classes of structures. In this paper we study first-order (FO) transductions and the q…
Rankwidth meets stability
Jaroslav Nesetril, Patrice Ossona de Mendez, Michal Pilipczuk +2
We study two notions of being well-structured for classes of graphs that are inspired by classic model theory. A class of graphs is monadically stable if it is impossible to de…
Elimination distance to bounded degree on planar graphs
Alexander Lindermayr, Sebastian Siebertz, Alexandre Vigny
We study the graph parameter elimination distance to bounded degree, which was introduced by Bulian and Dawar in their study of the parameterized complexity of the graph isomorphis…
Regular partitions of gentle graphs
Yiting Jiang, Jaroslav Nesetril, Patrice Ossona de Mendez +1
Szemeredi's Regularity Lemma is a very useful tool of extremal combinatorics. Recently, several refinements of this seminal result were obtained for special, more structured classe…