Submitted/in Preparation
M. Pilipczuk, S. Siebertz
Kernelization and approximation of distance-r independent sets on nowhere dense graphs
Available online.
2019
G. Fabiański, M. Pilipczuk, S. Siebertz, S. Toruńczyk.
Progressive Algorithms for Domination and Independence
STACS 2019: 27:1-27:16. Available online.
S. Kreutzer, I. Muzi, P. Ossona de Mendez, R. Rabinovich, S. Siebertz.
Algorithmic Properties of Sparse Digraphs.
STACS 2019: 46:1-46:20. Available online.
S. Akhoondian Amiri, Stefan Schmid, and S. Siebertz.
Distributed Dominating Set Approximations
beyond Planar Graphs.
ACM Trans. Algorithms 15(3): 39:1-39:18 (2019). Available online.
M. Pilipczuk and S. Siebertz.
Polynomial bounds for centered colorings on proper
minor-closed graph classes.
SODA 2019: 1501-1520. Available online.
S. Siebertz
Greedy domination on biclique-free graphs
Inf. Process. Lett. 145: 64-67 (2019). Available online.
E. Eiben, M. Kumar, A. E. Mouawad, F. Panolan, S. Siebertz
Lossy Kernels for Connected Dominating Set on Sparse Graphs
SIAM J. Discrete Math. 33(3): 1743-1771 (2019). Available online
2018
S. Kreutzer, R. Rabinovich, S. Siebertz.
Polynomial kernels and wideness properties of nowhere dense
graph classes.
ACM Transactions on Algorithms (TALG), Volume 15 Issue 2,
2018. Available online.
M. Grohe, S. Kreutzer, R. Rabinovich, S. Siebertz,
K. Stavropoulos
Coloring and Covering Nowhere Dense Graphs.
SIAM Journal on Discrete Mathematics (SIDMA), Volume 32(4), 2018.
Available online.
J.Gajarsky, S. Kreutzer, J. Nestril, P. Ossona de Mendez,
M. Pilipczuk, S. Siebertz, S.Torunczyk.
First-order interpretations of bounded expansion
classes.
45th International Colloquium on Automata, Languages, and
Programming, ICALP 2018. Available online.
S. Siebertz.
Reconfiguration on nowhere dense graph classes
The Electronic Journal of Combinatorics, Volume 25, 2018. Available online.
M. Pilipczuk, S. Siebertz, and S. Torunczyk.
Parameterized circuit complexity of model-checking on sparse structures.
33rd Annual ACM/IEEE Symposium on Logic in Computer Science,
LICS 2018. Available online.
M. Pilipczuk, S. Siebertz, and S. Torunczyk.
On the number of types in sparse graphs
33rd Annual ACM/IEEE Symposium on Logic in Computer Science,
LICS 2018. Available online.
A. E. Mouawad, N. Nishimura, V. Raman, S. Siebertz.
Vertex Cover Reconfiguration and Beyond.
Algorithms 11(2), 2018. Available online.
S. Akhoondian Amiri, P. Ossona de Mendez, R. Rabinovich, and S. Siebertz.
Distributed Domination on Graph Classes of
Bounded Expansion.
30th ACM Symposium on Parallelism in
Algorithms and Architectures, SPAA 2018. Avalable online.
W. Nadara, Ma. Pilipczuk, R. Rabinovich, F. Reidl, S. Siebertz.
Empirical Evaluation of Approximation Algorithms for
Generalized Graph Coloring and Uniform Quasi-Wideness.
17th International Symposium on Experimental Algorithms, SEA
2018.
Available online
E. Eiben, M. Kumar, A. E. Mouawad, F. Panolan and S. Siebertz.
Lossy kernels for connected dominating set on sparse
graphs.
35th International Symposium on Theoretical Aspects of
Computer Science, STACS 2018. Available online
2017
M. Grohe, S. Kreutzer, and S. Siebertz.
Deciding first-order properties of nowhere dense graphs.
Journal of the ACM, 2017. Available online.
J. van den Heuvel, P. Ossona de Mendez, Daniel A. Quiroz, R. Rabinovich, and
S. Siebertz.
On the generalised
colouring numbers of graphs that exclude a fixed minor.
European Journal
of Combinatorics, 2017. Available online.
O. Kwon, M. Pilipczuk, and S. Siebertz.
On Low Rank-Width Colorings
43rd International Workshop on Graph-Theoretic Concepts in
Computer Science, WG 2017. Available online.
K. Eickmeyer, A. Giannopoulou, S. Kreutzer, O. Kwon, M. Pilipczuk,
R. Rabinovich, and S. Siebertz.
Neighborhood complexity and kernelization
for nowhere dense classes of graphs.
44th International Colloquium on Automata,
Languages, and Programming, ICALP 2017. Available online.
S. Kreutzer, R. Rabinovich, S. Siebertz, and G. Weberstädt.
Structural Properties and
Constant Factor-Approximation of Strong Distance-r Dominating Sets in Sparse Directed
Graphs.
34th International Symposium on Theoretical Aspects of
Computer Science, STACS 2017. Available online.
J. van den Heuvel, S. Kreutzer, M. Pilipczuk, D. A. Quiroz,
R. Rabinovich, and S. Siebertz.
Successor-invariant model-checking on classes of bounded
expansion
32nd Annual ACM/IEEE Symposium on
Logic in Computer Science, LICS 2017. Available online.
S. Kreutzer, R. Rabinovich, and S. Siebertz.
Polynomial Kernels and Wideness Properties
of Nowhere Dense Graph Classes.
28th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA
2017. Available online.
2016
S. Akhoondian Amiri, S. Schmid, and S. Siebertz.
A local constant factor approximation for the
minimum dominating set problem on bounded genus graphs.
ACM Symposium on Principles
of Distributed Computing, PODC 2016. Available online.
P. G. Drange, M. S. Dregi, F. V. Fomin, S. Kreutzer, D. Lokshtanov, M. Pilipczuk, M. Pilipczuk,
F. Reidl, S. Saurabh, S. Siebertz, F.S. Villaamil and S.Sikdar.
Kernelization and sparseness:
the case of dominating set.
33rd International Symposium on Theoretical Aspects of Computer
Science, STACS 2016. Available online.
S. Kreutzer, M. Pilipczuk, R. Rabinovich, and S. Siebertz.
The generalised colouring numbers
on classes of bounded expansion.
41st International Symposium on Mathematical Foundations
of Computer Science, MFCS 2016. Available online.
S. Siebertz.
Nowhere Dense Classes of Graphs: Characterisations and Algorithmic Meta-
Theorems.
Doctoral Thesis. Universitätsverlag der TU Berlin, 2016. Available
online.
2015
S. Akhoondian Amiri, L. Kaiser, S. Kreutzer, R. Rabinovich and
S. Siebertz.
Graph searching
games and width measures for directed graphs.
32nd Symposium on Theoretical Aspects of
Computer Science, STACS 2015. Available online.
M. Grohe, S. Kreutzer, R. Rabinovich, S. Siebertz and
K. Stavropoulos.
Colouring and
covering nowhere dense graphs.
41st International Workshop on Graph-Theoretic Concepts in
Computer Science, WG 2015. Available online.
J. van den Heuvel, P. Ossona de Mendez, R. Rabinovich and
S. Siebertz.
On the generalised
colouring numbers of graphs that exclude a fixed minor.
Electronic Notes in Discrete
Mathematics, 2015. Available online.
2014
S. Akhoondian Amiri, A. Golshani, S. Kreutzer and S. Siebertz.
Vertex disjoint paths in
upward planar graphs.
The 9th International Computer Science Symposium in Russia, CSR
2014. Available online.
M. Grohe, S. Kreutzer and S. Siebertz.
Deciding first-order properties of nowhere dense graphs.
46th Annual Symposium on the Theory of Computing, STOC 2014.
Available online.
2013
M. Grohe, S. Kreutzer and S. Siebertz.
Characterisations of nowhere dense graphs (invited
talk).
ARCS Annual Conference on Foundations of Software Technology and Theoretical
Computer Science, FSTTCS 2013. Available online.
2012
V. Engelmann, S. Kreutzer and S. Siebertz.
First-order and monadic second-order modelchecking
on ordered structures.
27th Annual ACM/IEEE Symposium on Logic in Computer
Science, LICS 2012. Available online.
E. Grädel and S. Siebertz.
Dynamic definability.
15th International Conference on Database
Theory, ICDT 2012. Available online.
2011
S. Siebertz.
Dynamic Definability.
Diploma thesis, RWTH Aachen, 2011.