4 papers
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…
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…
The Generalised Colouring Numbers on Classes of Bounded Expansion
Stephan Kreutzer, Michał Pilipczuk, Roman Rabinovich +1
The generalised colouring numbers , , and were introduced by Kierstead and Yang as generalisations of the usual colouring…
A local constant factor approximation for the minimum dominating set problem on bounded genus graphs
Saeed Akhoondian Amiri, Stefan Schmid, Sebastian Siebertz
The Minimum Dominating Set (MDS) problem is not only one of the most fundamental problems in distributed computing, it is also one of the most challenging ones. While it is well-kn…