6 citations · 14 across the 10 of their papers we have counts for
4 papers · 1 filter
Distributed domination on sparse graph classes
Ozan Heydt, Simeon Kublenz, Patrice Ossona de Mendez +2
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…
Combinatorial and Algorithmic Aspects of Monadic Stability
Jan Dreier, Nikolas Mählmann, Amer E. Mouawad +2
Nowhere dense classes of graphs are classes of sparse graphs with rich structural and algorithmic properties, however, they fail to capture even simple classes of dense graphs. Mon…
Neighborhood complexity and kernelization for nowhere dense classes of graphs
Kord Eickmeyer, Archontia C. Giannopoulou, Stephan Kreutzer +4
We prove that whenever is a graph from a nowhere dense graph class , and is a subset of vertices of , then the number of subsets of that are realized as…
Directed Width Measures and Monotonicity of Directed Graph Searching
Łukasz Kaiser, Stephan Kreutzer, Roman Rabinovich +1
We consider generalisations of tree width to directed graphs, that attracted much attention in the last fifteen years. About their relative strength with respect to "bounded width…