LIPIcs, Volume 41
CSL 2015, September 7-10, 2015, Berlin, Germany
Editors: Stephan Kreutzer
Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)
Jan Dreier, Nikolas Mählmann, Sebastian Siebertz, and Szymon Toruńczyk. Indiscernibles and Flatness in Monadically Stable and Monadically NIP Classes. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 125:1-125:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{dreier_et_al:LIPIcs.ICALP.2023.125, author = {Dreier, Jan and M\"{a}hlmann, Nikolas and Siebertz, Sebastian and Toru\'{n}czyk, Szymon}, title = {{Indiscernibles and Flatness in Monadically Stable and Monadically NIP Classes}}, booktitle = {50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)}, pages = {125:1--125:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-278-5}, ISSN = {1868-8969}, year = {2023}, volume = {261}, editor = {Etessami, Kousha and Feige, Uriel and Puppis, Gabriele}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.125}, URN = {urn:nbn:de:0030-drops-181779}, doi = {10.4230/LIPIcs.ICALP.2023.125}, annote = {Keywords: stability, NIP, combinatorial characterization, first-order model checking} }
Published in: LIPIcs, Volume 216, 30th EACSL Annual Conference on Computer Science Logic (CSL 2022)
Jakub Gajarský, Maximilian Gorsky, and Stephan Kreutzer. Differential Games, Locality, and Model Checking for FO Logic of Graphs. In 30th EACSL Annual Conference on Computer Science Logic (CSL 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 216, pp. 22:1-22:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{gajarsky_et_al:LIPIcs.CSL.2022.22, author = {Gajarsk\'{y}, Jakub and Gorsky, Maximilian and Kreutzer, Stephan}, title = {{Differential Games, Locality, and Model Checking for FO Logic of Graphs}}, booktitle = {30th EACSL Annual Conference on Computer Science Logic (CSL 2022)}, pages = {22:1--22:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-218-1}, ISSN = {1868-8969}, year = {2022}, volume = {216}, editor = {Manea, Florin and Simpson, Alex}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2022.22}, URN = {urn:nbn:de:0030-drops-157426}, doi = {10.4230/LIPIcs.CSL.2022.22}, annote = {Keywords: FO model checking, locality, Gaifman’s theorem, EF games} }
Published in: LIPIcs, Volume 154, 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)
Jakub Gajarský and Stephan Kreutzer. Computing Shrub-Depth Decompositions. In 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 154, pp. 56:1-56:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{gajarsky_et_al:LIPIcs.STACS.2020.56, author = {Gajarsk\'{y}, Jakub and Kreutzer, Stephan}, title = {{Computing Shrub-Depth Decompositions}}, booktitle = {37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)}, pages = {56:1--56:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-140-5}, ISSN = {1868-8969}, year = {2020}, volume = {154}, editor = {Paul, Christophe and Bl\"{a}ser, Markus}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2020.56}, URN = {urn:nbn:de:0030-drops-119177}, doi = {10.4230/LIPIcs.STACS.2020.56}, annote = {Keywords: shrub-depth, tree-model, decomposition, fixed-parameter tractability} }
Published in: LIPIcs, Volume 144, 27th Annual European Symposium on Algorithms (ESA 2019)
Tomáš Masařík, Irene Muzi, Marcin Pilipczuk, Paweł Rzążewski, and Manuel Sorge. Packing Directed Circuits Quarter-Integrally. In 27th Annual European Symposium on Algorithms (ESA 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 144, pp. 72:1-72:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{masarik_et_al:LIPIcs.ESA.2019.72, author = {Masa\v{r}{\'\i}k, Tom\'{a}\v{s} and Muzi, Irene and Pilipczuk, Marcin and Rz\k{a}\.{z}ewski, Pawe{\l} and Sorge, Manuel}, title = {{Packing Directed Circuits Quarter-Integrally}}, booktitle = {27th Annual European Symposium on Algorithms (ESA 2019)}, pages = {72:1--72:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-124-5}, ISSN = {1868-8969}, year = {2019}, volume = {144}, editor = {Bender, Michael A. and Svensson, Ola and Herman, Grzegorz}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2019.72}, URN = {urn:nbn:de:0030-drops-111938}, doi = {10.4230/LIPIcs.ESA.2019.72}, annote = {Keywords: Directed graphs, graph algorithms, linkage, Erd\H{o}s–P\'{o}sa property} }
Published in: LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)
Holger Dell, Marc Roth, and Philip Wellnitz. Counting Answers to Existential Questions (Track B: Automata, Logic, Semantics, and Theory of Programming). In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 113:1-113:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{dell_et_al:LIPIcs.ICALP.2019.113, author = {Dell, Holger and Roth, Marc and Wellnitz, Philip}, title = {{Counting Answers to Existential Questions}}, booktitle = {46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)}, pages = {113:1--113:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-109-2}, ISSN = {1868-8969}, year = {2019}, volume = {132}, editor = {Baier, Christel and Chatzigiannakis, Ioannis and Flocchini, Paola and Leonardi, Stefano}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.113}, URN = {urn:nbn:de:0030-drops-106894}, doi = {10.4230/LIPIcs.ICALP.2019.113}, annote = {Keywords: Conjunctive queries, graph homomorphisms, counting complexity, parameterized complexity, fine-grained complexity} }
Published in: LIPIcs, Volume 126, 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)
Stephan Kreutzer, Irene Muzi, Patrice Ossona de Mendez, Roman Rabinovich, and Sebastian Siebertz. Algorithmic Properties of Sparse Digraphs. In 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 126, pp. 46:1-46:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{kreutzer_et_al:LIPIcs.STACS.2019.46, author = {Kreutzer, Stephan and Muzi, Irene and Ossona de Mendez, Patrice and Rabinovich, Roman and Siebertz, Sebastian}, title = {{Algorithmic Properties of Sparse Digraphs}}, booktitle = {36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)}, pages = {46:1--46:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-100-9}, ISSN = {1868-8969}, year = {2019}, volume = {126}, editor = {Niedermeier, Rolf and Paul, Christophe}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2019.46}, URN = {urn:nbn:de:0030-drops-102859}, doi = {10.4230/LIPIcs.STACS.2019.46}, annote = {Keywords: Directed graphs, graph algorithms, parameterized complexity, approximation} }
Published in: LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)
Albert Atserias, Stephan Kreutzer, and Marc Noy. On Zero-One and Convergence Laws for Graphs Embeddable on a Fixed Surface. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 116:1-116:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{atserias_et_al:LIPIcs.ICALP.2018.116, author = {Atserias, Albert and Kreutzer, Stephan and Noy, Marc}, title = {{On Zero-One and Convergence Laws for Graphs Embeddable on a Fixed Surface}}, booktitle = {45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)}, pages = {116:1--116:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-076-7}, ISSN = {1868-8969}, year = {2018}, volume = {107}, editor = {Chatzigiannakis, Ioannis and Kaklamanis, Christos and Marx, D\'{a}niel and Sannella, Donald}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.116}, URN = {urn:nbn:de:0030-drops-91206}, doi = {10.4230/LIPIcs.ICALP.2018.116}, annote = {Keywords: topological graph theory, monadic second-order logic, random graphs, zero-one law, convergence law} }
Published in: LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)
Jakub Gajarský, Stephan Kreutzer, Jaroslav Nesetril, Patrice Ossona de Mendez, Michal Pilipczuk, Sebastian Siebertz, and Szymon Torunczyk. First-Order Interpretations of Bounded Expansion Classes. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 126:1-126:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{gajarsky_et_al:LIPIcs.ICALP.2018.126, author = {Gajarsk\'{y}, Jakub and Kreutzer, Stephan and Nesetril, Jaroslav and Ossona de Mendez, Patrice and Pilipczuk, Michal and Siebertz, Sebastian and Torunczyk, Szymon}, title = {{First-Order Interpretations of Bounded Expansion Classes}}, booktitle = {45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)}, pages = {126:1--126:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-076-7}, ISSN = {1868-8969}, year = {2018}, volume = {107}, editor = {Chatzigiannakis, Ioannis and Kaklamanis, Christos and Marx, D\'{a}niel and Sannella, Donald}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.126}, URN = {urn:nbn:de:0030-drops-91300}, doi = {10.4230/LIPIcs.ICALP.2018.126}, annote = {Keywords: Logical interpretations/transductions, structurally sparse graphs, bounded expansion} }
Published in: LIPIcs, Volume 82, 26th EACSL Annual Conference on Computer Science Logic (CSL 2017)
Stephan Kreutzer. Current Trends and New Perspectives for First-Order Model Checking (Invited Talk). In 26th EACSL Annual Conference on Computer Science Logic (CSL 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 82, pp. 4:1-4:5, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{kreutzer:LIPIcs.CSL.2017.4, author = {Kreutzer, Stephan}, title = {{Current Trends and New Perspectives for First-Order Model Checking}}, booktitle = {26th EACSL Annual Conference on Computer Science Logic (CSL 2017)}, pages = {4:1--4:5}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-045-3}, ISSN = {1868-8969}, year = {2017}, volume = {82}, editor = {Goranko, Valentin and Dam, Mads}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2017.4}, URN = {urn:nbn:de:0030-drops-77095}, doi = {10.4230/LIPIcs.CSL.2017.4}, annote = {Keywords: Finite Model Theory, Computational Model Theory, Algorithmic Meta Theorems, Model-Checking, Logical Approaches in Graph Theory} }
Published in: LIPIcs, Volume 80, 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)
Kord Eickmeyer, Archontia C. Giannopoulou, Stephan Kreutzer, O-joung Kwon, Michal Pilipczuk, Roman Rabinovich, and Sebastian Siebertz. Neighborhood Complexity and Kernelization for Nowhere Dense Classes of Graphs. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 80, pp. 63:1-63:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{eickmeyer_et_al:LIPIcs.ICALP.2017.63, author = {Eickmeyer, Kord and Giannopoulou, Archontia C. and Kreutzer, Stephan and Kwon, O-joung and Pilipczuk, Michal and Rabinovich, Roman and Siebertz, Sebastian}, title = {{Neighborhood Complexity and Kernelization for Nowhere Dense Classes of Graphs}}, booktitle = {44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)}, pages = {63:1--63:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-041-5}, ISSN = {1868-8969}, year = {2017}, volume = {80}, editor = {Chatzigiannakis, Ioannis and Indyk, Piotr and Kuhn, Fabian and Muscholl, Anca}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2017.63}, URN = {urn:nbn:de:0030-drops-74288}, doi = {10.4230/LIPIcs.ICALP.2017.63}, annote = {Keywords: Graph Structure Theory, Nowhere Dense Graphs, Parameterized Complexity, Kernelization, Dominating Set} }
Published in: LIPIcs, Volume 66, 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)
Stephan Kreutzer, Roman Rabinovich, Sebastian Siebertz, and Grischa Weberstädt. Structural Properties and Constant Factor-Approximation of Strong Distance-r Dominating Sets in Sparse Directed Graphs. In 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 66, pp. 48:1-48:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{kreutzer_et_al:LIPIcs.STACS.2017.48, author = {Kreutzer, Stephan and Rabinovich, Roman and Siebertz, Sebastian and Weberst\"{a}dt, Grischa}, title = {{Structural Properties and Constant Factor-Approximation of Strong Distance-r Dominating Sets in Sparse Directed Graphs}}, booktitle = {34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)}, pages = {48:1--48:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-028-6}, ISSN = {1868-8969}, year = {2017}, volume = {66}, editor = {Vollmer, Heribert and Vall\'{e}e, Brigitte}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2017.48}, URN = {urn:nbn:de:0030-drops-69868}, doi = {10.4230/LIPIcs.STACS.2017.48}, annote = {Keywords: Directed Graph Structure Theory, Bounded Expansion, Generalised Colouring Numbers, Splitter Game, Approximation Algorithms, Dominating Set} }
Published in: LIPIcs, Volume 58, 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)
Saeed Akhoondian Amiri, Stephan Kreutzer, Dániel Marx, and Roman Rabinovich. Routing with Congestion in Acyclic Digraphs. In 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 58, pp. 7:1-7:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
@InProceedings{amiri_et_al:LIPIcs.MFCS.2016.7, author = {Amiri, Saeed Akhoondian and Kreutzer, Stephan and Marx, D\'{a}niel and Rabinovich, Roman}, title = {{Routing with Congestion in Acyclic Digraphs}}, booktitle = {41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)}, pages = {7:1--7:11}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-016-3}, ISSN = {1868-8969}, year = {2016}, volume = {58}, editor = {Faliszewski, Piotr and Muscholl, Anca and Niedermeier, Rolf}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2016.7}, URN = {urn:nbn:de:0030-drops-64244}, doi = {10.4230/LIPIcs.MFCS.2016.7}, annote = {Keywords: algorithms, disjoint paths, congestion, acyclic digraphs, XP, W\lbrack1\rbrack-hard} }
Published in: LIPIcs, Volume 58, 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)
Stephan Kreutzer, Michal Pilipczuk, Roman Rabinovich, and Sebastian Siebertz. The Generalised Colouring Numbers on Classes of Bounded Expansion. In 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 58, pp. 85:1-85:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
@InProceedings{kreutzer_et_al:LIPIcs.MFCS.2016.85, author = {Kreutzer, Stephan and Pilipczuk, Michal and Rabinovich, Roman and Siebertz, Sebastian}, title = {{The Generalised Colouring Numbers on Classes of Bounded Expansion}}, booktitle = {41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)}, pages = {85:1--85:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-016-3}, ISSN = {1868-8969}, year = {2016}, volume = {58}, editor = {Faliszewski, Piotr and Muscholl, Anca and Niedermeier, Rolf}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2016.85}, URN = {urn:nbn:de:0030-drops-64937}, doi = {10.4230/LIPIcs.MFCS.2016.85}, annote = {Keywords: graph structure theory, nowhere dense graphs, generalised colouring numbers, splitter game, first-order model-checking} }
Published in: LIPIcs, Volume 47, 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016)
Pål Grønås Drange, Markus Dregi, Fedor V. Fomin, Stephan Kreutzer, Daniel Lokshtanov, Marcin Pilipczuk, Michal Pilipczuk, Felix Reidl, Fernando Sánchez Villaamil, Saket Saurabh, Sebastian Siebertz, and Somnath Sikdar. Kernelization and Sparseness: the Case of Dominating Set. In 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 47, pp. 31:1-31:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
@InProceedings{drange_et_al:LIPIcs.STACS.2016.31, author = {Drange, P\r{a}l Gr{\o}n\r{a}s and Dregi, Markus and Fomin, Fedor V. and Kreutzer, Stephan and Lokshtanov, Daniel and Pilipczuk, Marcin and Pilipczuk, Michal and Reidl, Felix and S\'{a}nchez Villaamil, Fernando and Saurabh, Saket and Siebertz, Sebastian and Sikdar, Somnath}, title = {{Kernelization and Sparseness: the Case of Dominating Set}}, booktitle = {33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016)}, pages = {31:1--31:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-001-9}, ISSN = {1868-8969}, year = {2016}, volume = {47}, editor = {Ollinger, Nicolas and Vollmer, Heribert}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2016.31}, URN = {urn:nbn:de:0030-drops-57327}, doi = {10.4230/LIPIcs.STACS.2016.31}, annote = {Keywords: kernelization, dominating set, bounded expansion, nowhere dense} }
Feedback for Dagstuhl Publishing