Skip to main content

Publications

2022

2021

2020

  • O-joung Kwon, Michal Pilipczuk, Sebastian Siebertz:
    On low rank-width colorings. Eur. J. Comb. 83 (2020)
  • Kord Eickmeyer, Jan van den Heuvel, Ken-ichi Kawarabayashi, Stephan Kreutzer, Patrice Ossona de Mendez, Michal Pilipczuk, Daniel A. Quiroz, Roman Rabinovich, Sebastian Siebertz:
    Model-Checking on Ordered Structures. ACM Trans. Comput. Log. 21(2): 11:1-11:28 (2020)
  • Jakub Gajarský, Stephan Kreutzer, Jaroslav Nesetril, Patrice Ossona de Mendez, Michal Pilipczuk, Sebastian Siebertz, Szymon Torunczyk:
    First-Order Interpretations of Bounded Expansion Classes. ACM Trans. Comput. Log. 21(4): 29:1-29:41 (2020)
  • Daniel Lokshtanov, Amer E. Mouawad, Fahad Panolan, Sebastian Siebertz:
    On the Parameterized Complexity of Reconfiguration of Connected Dominating Sets. IPEC 2020: 24:1-24:15
  • Alexander Lindermayr, Sebastian Siebertz, Alexandre Vigny:
    Elimination Distance to Bounded Degree on Planar Graphs. MFCS 2020: 65:1-65:12
  • Jaroslav Nesetril, Roman Rabinovich, Patrice Ossona de Mendez, Sebastian Siebertz:
    Linear rankwidth meets stability. SODA 2020: 1180-1199

2019

  • Sebastian Siebertz:
    Greedy domination on biclique-free graphs. Inf. Process. Lett. 145: 64-67 (2019)
  • Wojciech Nadara, Marcin Pilipczuk, Roman Rabinovich, Felix Reidl, Sebastian Siebertz:
    Empirical Evaluation of Approximation Algorithms for Generalized Graph Coloring and Uniform Quasi-wideness. ACM J. Exp. Algorithmics 24(1): 2.6:1-2.6:34 (2019)
  • Eduard Eiben, Mithilesh Kumar, Amer E. Mouawad, Fahad Panolan, Sebastian Siebertz:
    Lossy Kernels for Connected Dominating Set on Sparse Graphs. SIAM J. Discret. Math. 33(3): 1743-1771 (2019)
  • Stephan Kreutzer, Roman Rabinovich, Sebastian Siebertz:
    Polynomial Kernels and Wideness Properties of Nowhere Dense Graph Classes. ACM Trans. Algorithms 15(2): 24:1-24:19 (2019)
  • Saeed Akhoondian Amiri, Stefan Schmid, Sebastian Siebertz:
    Distributed Dominating Set Approximations beyond Planar Graphs. ACM Trans. Algorithms 15(3): 39:1-39:18 (2019)
  • Michal Pilipczuk, Sebastian Siebertz:
    Polynomial bounds for centered colorings on proper minor-closed graph classes. SODA 2019: 1501-1520
  • Grzegorz Fabianski, Michal Pilipczuk, Sebastian Siebertz, Szymon Torunczyk:
    Progressive Algorithms for Domination and Independence. STACS 2019: 27:1-27:16
  • Stephan Kreutzer, Irene Muzi, Patrice Ossona de Mendez, Roman Rabinovich, Sebastian Siebertz:
    Algorithmic Properties of Sparse Digraphs. STACS 2019: 46:1-46:20

2018

  • Amer E. Mouawad, Naomi Nishimura, Venkatesh Raman, Sebastian Siebertz:
    Vertex Cover Reconfiguration and Beyond. Algorithms 11(2): 20 (2018)
  • Sebastian Siebertz:
    Reconfiguration on Nowhere Dense Graph Classes. Electron. J. Comb. 25(3): P3.24 (2018)
  • Martin Grohe, Stephan Kreutzer, Roman Rabinovich, Sebastian Siebertz, Konstantinos S. Stavropoulos:
    Coloring and Covering Nowhere Dense Graphs. SIAM J. Discret. Math. 32(4): 2467-2481 (2018)
  • Jakub Gajarský, Stephan Kreutzer, Jaroslav Nesetril, Patrice Ossona de Mendez, Michal Pilipczuk, Sebastian Siebertz, Szymon Torunczyk:
    First-Order Interpretations of Bounded Expansion Classes. ICALP 2018: 126:1-126:14
  • Michal Pilipczuk, Sebastian Siebertz, Szymon Torunczyk:
    Parameterized circuit complexity of model-checking on sparse structures. LICS 2018: 789-798
  • Michal Pilipczuk, Sebastian Siebertz, Szymon Torunczyk:
    On the number of types in sparse graphs. LICS 2018: 799-808
  • Saeed Akhoondian Amiri, Patrice Ossona de Mendez, Roman Rabinovich, Sebastian Siebertz:
    Distributed Domination on Graph Classes of Bounded Expansion. SPAA 2018: 143-151
  • Eduard Eiben, Mithilesh Kumar, Amer E. Mouawad, Fahad Panolan, Sebastian Siebertz:
    Lossy Kernels for Connected Dominating Set on Sparse Graphs. STACS 2018: 29:1-29:15
  • Wojciech Nadara, Marcin Pilipczuk, Roman Rabinovich, Felix Reidl, Sebastian Siebertz:
    Empirical Evaluation of Approximation Algorithms for Generalized Graph Coloring and Uniform Quasi-Wideness. SEA 2018: 14:1-14:16
  •  

2017

  • Jan van den Heuvel, Patrice Ossona de Mendez, Daniel Quiroz, Roman Rabinovich, Sebastian Siebertz:
    On the generalised colouring numbers of graphs that exclude a fixed minor. Eur. J. Comb. 66: 129-144 (2017)
  • Martin Grohe, Stephan Kreutzer, Sebastian Siebertz:
    Deciding First-Order Properties of Nowhere Dense Graphs. J. ACM 64(3): 17:1-17:32 (2017)
  • Kord Eickmeyer, Archontia C. Giannopoulou, Stephan Kreutzer, O-joung Kwon, Michal Pilipczuk, Roman Rabinovich, Sebastian Siebertz:
    Neighborhood Complexity and Kernelization for Nowhere Dense Classes of Graphs. ICALP 2017: 63:1-63:14
  • Jan van den Heuvel, Stephan Kreutzer, Michal Pilipczuk, Daniel A. Quiroz, Roman Rabinovich, Sebastian Siebertz:
    Model-checking for successor-invariant first-order formulas on graph classes of bounded expansion. LICS 2017: 1-11
  • Stephan Kreutzer, Roman Rabinovich, Sebastian Siebertz:
    Polynomial Kernels and Wideness Properties of Nowhere Dense Graph Classes. SODA 2017: 1533-1545
  • Stephan Kreutzer, Roman Rabinovich, Sebastian Siebertz, Grischa Weberstädt:
    Structural Properties and Constant Factor-Approximation of Strong Distance-r Dominating Sets in Sparse Directed Graphs. STACS 2017: 48:1-48:15
  • O-joung Kwon, Michal Pilipczuk, Sebastian Siebertz:
    On Low Rank-Width Colorings. WG 2017: 372-385

2016

  • Stephan Kreutzer, Michal Pilipczuk, Roman Rabinovich, Sebastian Siebertz:
    The Generalised Colouring Numbers on Classes of Bounded Expansion. MFCS 2016: 85:1-85:13
  • Saeed Akhoondian Amiri, Stefan Schmid, Sebastian Siebertz:
    A Local Constant Factor MDS Approximation for Bounded Genus Graphs. PODC 2016: 227-233
  • Pål Grønås Drange, Markus Sortland Dregi, Fedor V. Fomin, Stephan Kreutzer, Daniel Lokshtanov, Marcin Pilipczuk, Michal Pilipczuk, Felix Reidl, Fernando Sánchez Villaamil, Saket Saurabh, Sebastian Siebertz, Somnath Sikdar:
    Kernelization and Sparseness: the Case of Dominating Set. STACS 2016: 31:1-31:14

2015

  • Jan van den Heuvel, Patrice Ossona de Mendez, Roman Rabinovich, Sebastian Siebertz:
    On the generalised colouring numbers of graphs that exclude a fixed minor. Electron. Notes Discret. Math. 49: 523-530 (2015)
  • Saeed Akhoondian Amiri, Lukasz Kaiser, Stephan Kreutzer, Roman Rabinovich, Sebastian Siebertz:
    Graph Searching Games and Width Measures for Directed Graphs. STACS 2015: 34-47
  • Martin Grohe, Stephan Kreutzer, Roman Rabinovich, Sebastian Siebertz, Konstantinos S. Stavropoulos:
    Colouring and Covering Nowhere Dense Graphs. WG 2015: 325-338

2014

  • Saeed Akhoondian Amiri, Ali Golshani, Stephan Kreutzer, Sebastian Siebertz:
    Vertex Disjoint Paths in Upward Planar Graphs. CSR 2014: 52-64
  • Martin Grohe, Stephan Kreutzer, Sebastian Siebertz:
    Deciding first-order properties of nowhere dense graphs. STOC 2014: 89-98

2013

  • Martin Grohe, Stephan Kreutzer, Sebastian Siebertz:
    Characterisations of Nowhere Dense Graphs (Invited Talk). FSTTCS 2013: 21-40

2012

  • Erich Grädel, Sebastian Siebertz:
    Dynamic definability. ICDT 2012: 236-248
  • Viktor Engelmann, Stephan Kreutzer, Sebastian Siebertz:
    First-Order and Monadic Second-Order Model-Checking on Ordered Structures. LICS 2012: 275-284