LIPIcs, Volume 115
IPEC 2018, August 20-24, 2018, Helsinki, Finland
Editors: Christophe Paul and Michal Pilipczuk
Published in: LIPIcs, Volume 285, 18th International Symposium on Parameterized and Exact Computation (IPEC 2023)
Mathieu Mari, Timothé Picavet, and Michał Pilipczuk. A Parameterized Approximation Scheme for the Geometric Knapsack Problem with Wide Items. In 18th International Symposium on Parameterized and Exact Computation (IPEC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 285, pp. 33:1-33:20, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{mari_et_al:LIPIcs.IPEC.2023.33, author = {Mari, Mathieu and Picavet, Timoth\'{e} and Pilipczuk, Micha{\l}}, title = {{A Parameterized Approximation Scheme for the Geometric Knapsack Problem with Wide Items}}, booktitle = {18th International Symposium on Parameterized and Exact Computation (IPEC 2023)}, pages = {33:1--33:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-305-8}, ISSN = {1868-8969}, year = {2023}, volume = {285}, editor = {Misra, Neeldhara and Wahlstr\"{o}m, Magnus}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2023.33}, URN = {urn:nbn:de:0030-drops-194529}, doi = {10.4230/LIPIcs.IPEC.2023.33}, annote = {Keywords: Parameterized complexity, Approximation scheme, Geometric knapsack, Color coding, Dynamic programming, Computational geometry} }
Published in: LIPIcs, Volume 274, 31st Annual European Symposium on Algorithms (ESA 2023)
Benjamin Bergougnoux, Vera Chekan, Robert Ganian, Mamadou Moustapha Kanté, Matthias Mnich, Sang-il Oum, Michał Pilipczuk, and Erik Jan van Leeuwen. Space-Efficient Parameterized Algorithms on Graphs of Low Shrubdepth. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 18:1-18:18, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{bergougnoux_et_al:LIPIcs.ESA.2023.18, author = {Bergougnoux, Benjamin and Chekan, Vera and Ganian, Robert and Kant\'{e}, Mamadou Moustapha and Mnich, Matthias and Oum, Sang-il and Pilipczuk, Micha{\l} and van Leeuwen, Erik Jan}, title = {{Space-Efficient Parameterized Algorithms on Graphs of Low Shrubdepth}}, booktitle = {31st Annual European Symposium on Algorithms (ESA 2023)}, pages = {18:1--18:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-295-2}, ISSN = {1868-8969}, year = {2023}, volume = {274}, editor = {G{\o}rtz, Inge Li and Farach-Colton, Martin and Puglisi, Simon J. and Herman, Grzegorz}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2023.18}, URN = {urn:nbn:de:0030-drops-186710}, doi = {10.4230/LIPIcs.ESA.2023.18}, annote = {Keywords: Parameterized complexity, shrubdepth, space complexity, algebraic methods} }
Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)
Hans L. Bodlaender, Carla Groenland, and Michał Pilipczuk. Parameterized Complexity of Binary CSP: Vertex Cover, Treedepth, and Related Parameters. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 27:1-27:20, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{bodlaender_et_al:LIPIcs.ICALP.2023.27, author = {Bodlaender, Hans L. and Groenland, Carla and Pilipczuk, Micha{\l}}, title = {{Parameterized Complexity of Binary CSP: Vertex Cover, Treedepth, and Related Parameters}}, booktitle = {50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)}, pages = {27:1--27:20}, 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.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.27}, URN = {urn:nbn:de:0030-drops-180798}, doi = {10.4230/LIPIcs.ICALP.2023.27}, annote = {Keywords: Parameterized Complexity, Constraint Satisfaction Problems, Binary CSP, List Coloring, Vertex Cover, Treedepth, W-hierarchy} }
Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)
Jakub Gajarský, Nikolas Mählmann, Rose McCarty, Pierre Ohlmann, Michał Pilipczuk, Wojciech Przybyszewski, Sebastian Siebertz, Marek Sokołowski, and Szymon Toruńczyk. Flipper Games for Monadically Stable Graph Classes. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 128:1-128:16, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{gajarsky_et_al:LIPIcs.ICALP.2023.128, author = {Gajarsk\'{y}, Jakub and M\"{a}hlmann, Nikolas and McCarty, Rose and Ohlmann, Pierre and Pilipczuk, Micha{\l} and Przybyszewski, Wojciech and Siebertz, Sebastian and Soko{\l}owski, Marek and Toru\'{n}czyk, Szymon}, title = {{Flipper Games for Monadically Stable Graph Classes}}, booktitle = {50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)}, pages = {128:1--128:16}, 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.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.128}, URN = {urn:nbn:de:0030-drops-181804}, doi = {10.4230/LIPIcs.ICALP.2023.128}, annote = {Keywords: Stability theory, structural graph theory, games} }
Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)
Pierre Ohlmann, Michał Pilipczuk, Wojciech Przybyszewski, and Szymon Toruńczyk. Canonical Decompositions in Monadically Stable and Bounded Shrubdepth Graph Classes. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 135:1-135:17, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{ohlmann_et_al:LIPIcs.ICALP.2023.135, author = {Ohlmann, Pierre and Pilipczuk, Micha{\l} and Przybyszewski, Wojciech and Toru\'{n}czyk, Szymon}, title = {{Canonical Decompositions in Monadically Stable and Bounded Shrubdepth Graph Classes}}, booktitle = {50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)}, pages = {135:1--135:17}, 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.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.135}, URN = {urn:nbn:de:0030-drops-181874}, doi = {10.4230/LIPIcs.ICALP.2023.135}, annote = {Keywords: Model Theory, Stability Theory, Shrubdepth, Nowhere Dense, Monadically Stable} }
Published in: LIPIcs, Volume 254, 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)
Lorenzo Clemente, Maria Donten-Bury, Filip Mazowiecki, and Michał Pilipczuk. On Rational Recursive Sequences. In 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 254, pp. 24:1-24:21, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{clemente_et_al:LIPIcs.STACS.2023.24, author = {Clemente, Lorenzo and Donten-Bury, Maria and Mazowiecki, Filip and Pilipczuk, Micha{\l}}, title = {{On Rational Recursive Sequences}}, booktitle = {40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)}, pages = {24:1--24:21}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-266-2}, ISSN = {1868-8969}, year = {2023}, volume = {254}, editor = {Berenbrink, Petra and Bouyer, Patricia and Dawar, Anuj and Kant\'{e}, Mamadou Moustapha}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2023.24}, URN = {urn:nbn:de:0030-drops-176763}, doi = {10.4230/LIPIcs.STACS.2023.24}, annote = {Keywords: recursive sequences, polynomial automata, zeroness problem, equivalence problem} }
Published in: LIPIcs, Volume 254, 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)
Konrad Majewski, Michał Pilipczuk, and Marek Sokołowski. Maintaining CMSO₂ Properties on Dynamic Structures with Bounded Feedback Vertex Number. In 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 254, pp. 46:1-46:13, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{majewski_et_al:LIPIcs.STACS.2023.46, author = {Majewski, Konrad and Pilipczuk, Micha{\l} and Soko{\l}owski, Marek}, title = {{Maintaining CMSO₂ Properties on Dynamic Structures with Bounded Feedback Vertex Number}}, booktitle = {40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)}, pages = {46:1--46:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-266-2}, ISSN = {1868-8969}, year = {2023}, volume = {254}, editor = {Berenbrink, Petra and Bouyer, Patricia and Dawar, Anuj and Kant\'{e}, Mamadou Moustapha}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2023.46}, URN = {urn:nbn:de:0030-drops-176981}, doi = {10.4230/LIPIcs.STACS.2023.46}, annote = {Keywords: feedback vertex set, CMSO₂ formula, data structure, dynamic graphs, fixed-parameter tractability} }
Published in: LIPIcs, Volume 254, 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)
Jędrzej Olkowski, Michał Pilipczuk, Mateusz Rychlicki, Karol Węgrzycki, and Anna Zych-Pawlewicz. Dynamic Data Structures for Parameterized String Problems. In 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 254, pp. 50:1-50:22, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{olkowski_et_al:LIPIcs.STACS.2023.50, author = {Olkowski, J\k{e}drzej and Pilipczuk, Micha{\l} and Rychlicki, Mateusz and W\k{e}grzycki, Karol and Zych-Pawlewicz, Anna}, title = {{Dynamic Data Structures for Parameterized String Problems}}, booktitle = {40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)}, pages = {50:1--50:22}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-266-2}, ISSN = {1868-8969}, year = {2023}, volume = {254}, editor = {Berenbrink, Petra and Bouyer, Patricia and Dawar, Anuj and Kant\'{e}, Mamadou Moustapha}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2023.50}, URN = {urn:nbn:de:0030-drops-177026}, doi = {10.4230/LIPIcs.STACS.2023.50}, annote = {Keywords: Parameterized algorithms, Dynamic data structures, String problems, Closest String, Edit Distance, Disjoint Factors, Predecessor problem} }
Published in: LIPIcs, Volume 249, 17th International Symposium on Parameterized and Exact Computation (IPEC 2022)
Hans L. Bodlaender, Carla Groenland, Hugo Jacob, Marcin Pilipczuk, and Michał Pilipczuk. On the Complexity of Problems on Tree-Structured Graphs. In 17th International Symposium on Parameterized and Exact Computation (IPEC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 249, pp. 6:1-6:17, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{bodlaender_et_al:LIPIcs.IPEC.2022.6, author = {Bodlaender, Hans L. and Groenland, Carla and Jacob, Hugo and Pilipczuk, Marcin and Pilipczuk, Micha{\l}}, title = {{On the Complexity of Problems on Tree-Structured Graphs}}, booktitle = {17th International Symposium on Parameterized and Exact Computation (IPEC 2022)}, pages = {6:1--6:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-260-0}, ISSN = {1868-8969}, year = {2022}, volume = {249}, editor = {Dell, Holger and Nederlof, Jesper}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2022.6}, URN = {urn:nbn:de:0030-drops-173626}, doi = {10.4230/LIPIcs.IPEC.2022.6}, annote = {Keywords: Parameterized Complexity, Treewidth, XALP, XNLP} }
Published in: LIPIcs, Volume 244, 30th Annual European Symposium on Algorithms (ESA 2022)
Hans L. Bodlaender, Carla Groenland, and Hugo Jacob. List Colouring Trees in Logarithmic Space. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 24:1-24:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{bodlaender_et_al:LIPIcs.ESA.2022.24, author = {Bodlaender, Hans L. and Groenland, Carla and Jacob, Hugo}, title = {{List Colouring Trees in Logarithmic Space}}, booktitle = {30th Annual European Symposium on Algorithms (ESA 2022)}, pages = {24:1--24:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-247-1}, ISSN = {1868-8969}, year = {2022}, volume = {244}, editor = {Chechik, Shiri and Navarro, Gonzalo and Rotenberg, Eva and Herman, Grzegorz}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2022.24}, URN = {urn:nbn:de:0030-drops-169620}, doi = {10.4230/LIPIcs.ESA.2022.24}, annote = {Keywords: List colouring, trees, space complexity, logspace, graph algorithms, tree-partition-width} }
Published in: LIPIcs, Volume 244, 30th Annual European Symposium on Algorithms (ESA 2022)
Łukasz Bożyk and Michał Pilipczuk. Polynomial Kernel for Immersion Hitting in Tournaments. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 26:1-26:17, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{bozyk_et_al:LIPIcs.ESA.2022.26, author = {Bo\.{z}yk, {\L}ukasz and Pilipczuk, Micha{\l}}, title = {{Polynomial Kernel for Immersion Hitting in Tournaments}}, booktitle = {30th Annual European Symposium on Algorithms (ESA 2022)}, pages = {26:1--26:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-247-1}, ISSN = {1868-8969}, year = {2022}, volume = {244}, editor = {Chechik, Shiri and Navarro, Gonzalo and Rotenberg, Eva and Herman, Grzegorz}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2022.26}, URN = {urn:nbn:de:0030-drops-169642}, doi = {10.4230/LIPIcs.ESA.2022.26}, annote = {Keywords: kernelization, graph immersion, tournament, protrusion} }
Published in: LIPIcs, Volume 244, 30th Annual European Symposium on Algorithms (ESA 2022)
Wojciech Nadara, Michał Pilipczuk, and Marcin Smulewicz. Computing Treedepth in Polynomial Space and Linear FPT Time. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 79:1-79:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{nadara_et_al:LIPIcs.ESA.2022.79, author = {Nadara, Wojciech and Pilipczuk, Micha{\l} and Smulewicz, Marcin}, title = {{Computing Treedepth in Polynomial Space and Linear FPT Time}}, booktitle = {30th Annual European Symposium on Algorithms (ESA 2022)}, pages = {79:1--79:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-247-1}, ISSN = {1868-8969}, year = {2022}, volume = {244}, editor = {Chechik, Shiri and Navarro, Gonzalo and Rotenberg, Eva and Herman, Grzegorz}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2022.79}, URN = {urn:nbn:de:0030-drops-170175}, doi = {10.4230/LIPIcs.ESA.2022.79}, annote = {Keywords: treedepth, FPT, polynomial space} }
Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)
Michał Pilipczuk, Nicole Schirrmacher, Sebastian Siebertz, Szymon Toruńczyk, and Alexandre Vigny. Algorithms and Data Structures for First-Order Logic with Connectivity Under Vertex Failures. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 102:1-102:18, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{pilipczuk_et_al:LIPIcs.ICALP.2022.102, author = {Pilipczuk, Micha{\l} and Schirrmacher, Nicole and Siebertz, Sebastian and Toru\'{n}czyk, Szymon and Vigny, Alexandre}, title = {{Algorithms and Data Structures for First-Order Logic with Connectivity Under Vertex Failures}}, booktitle = {49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)}, pages = {102:1--102:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-235-8}, ISSN = {1868-8969}, year = {2022}, volume = {229}, editor = {Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.102}, URN = {urn:nbn:de:0030-drops-164432}, doi = {10.4230/LIPIcs.ICALP.2022.102}, annote = {Keywords: Combinatorics and graph theory, Computational applications of logic, Data structures, Fixed-parameter algorithms and complexity, Graph algorithms} }
Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)
Jakub Gajarský, Michał Pilipczuk, Wojciech Przybyszewski, and Szymon Toruńczyk. Twin-Width and Types. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 123:1-123:21, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{gajarsky_et_al:LIPIcs.ICALP.2022.123, author = {Gajarsk\'{y}, Jakub and Pilipczuk, Micha{\l} and Przybyszewski, Wojciech and Toru\'{n}czyk, Szymon}, title = {{Twin-Width and Types}}, booktitle = {49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)}, pages = {123:1--123:21}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-235-8}, ISSN = {1868-8969}, year = {2022}, volume = {229}, editor = {Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.123}, URN = {urn:nbn:de:0030-drops-164640}, doi = {10.4230/LIPIcs.ICALP.2022.123}, annote = {Keywords: twin-width, FO logic, model checking, query answering, enumeration} }
Feedback for Dagstuhl Publishing