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 254, 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)
Narek Bojikian, Vera Chekan, Falko Hegerfeld, and Stefan Kratsch. Tight Bounds for Connectivity Problems Parameterized by Cutwidth. In 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 254, pp. 14:1-14:16, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{bojikian_et_al:LIPIcs.STACS.2023.14, author = {Bojikian, Narek and Chekan, Vera and Hegerfeld, Falko and Kratsch, Stefan}, title = {{Tight Bounds for Connectivity Problems Parameterized by Cutwidth}}, booktitle = {40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)}, pages = {14:1--14:16}, 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.14}, URN = {urn:nbn:de:0030-drops-176667}, doi = {10.4230/LIPIcs.STACS.2023.14}, annote = {Keywords: Parameterized complexity, connectivity problems, cutwidth} }
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 249, 17th International Symposium on Parameterized and Exact Computation (IPEC 2022)
Hans L. Bodlaender, Carla Groenland, and Hugo Jacob. On the Parameterized Complexity of Computing Tree-Partitions. In 17th International Symposium on Parameterized and Exact Computation (IPEC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 249, pp. 7:1-7:20, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{bodlaender_et_al:LIPIcs.IPEC.2022.7, author = {Bodlaender, Hans L. and Groenland, Carla and Jacob, Hugo}, title = {{On the Parameterized Complexity of Computing Tree-Partitions}}, booktitle = {17th International Symposium on Parameterized and Exact Computation (IPEC 2022)}, pages = {7:1--7:20}, 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.7}, URN = {urn:nbn:de:0030-drops-173633}, doi = {10.4230/LIPIcs.IPEC.2022.7}, annote = {Keywords: Parameterized algorithms, Tree partitions, tree-partition-width, Treewidth, Domino Treewidth, Approximation Algorithms, Parameterized Complexity} }
Published in: LIPIcs, Volume 249, 17th International Symposium on Parameterized and Exact Computation (IPEC 2022)
Hans L. Bodlaender, Carla Groenland, Hugo Jacob, Lars Jaffke, and Paloma T. Lima. XNLP-Completeness for Parameterized Problems on Graphs with a Linear Structure. In 17th International Symposium on Parameterized and Exact Computation (IPEC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 249, pp. 8:1-8:18, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{bodlaender_et_al:LIPIcs.IPEC.2022.8, author = {Bodlaender, Hans L. and Groenland, Carla and Jacob, Hugo and Jaffke, Lars and Lima, Paloma T.}, title = {{XNLP-Completeness for Parameterized Problems on Graphs with a Linear Structure}}, booktitle = {17th International Symposium on Parameterized and Exact Computation (IPEC 2022)}, pages = {8:1--8:18}, 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.8}, URN = {urn:nbn:de:0030-drops-173640}, doi = {10.4230/LIPIcs.IPEC.2022.8}, annote = {Keywords: parameterized complexity, XNLP, linear clique-width, W-hierarchy, pathwidth, linear mim-width, bandwidth} }
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 219, 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)
Carla Groenland, Isja Mannens, Jesper Nederlof, and Krisztina Szilágyi. Tight Bounds for Counting Colorings and Connected Edge Sets Parameterized by Cutwidth. In 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 219, pp. 36:1-36:20, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{groenland_et_al:LIPIcs.STACS.2022.36, author = {Groenland, Carla and Mannens, Isja and Nederlof, Jesper and Szil\'{a}gyi, Krisztina}, title = {{Tight Bounds for Counting Colorings and Connected Edge Sets Parameterized by Cutwidth}}, booktitle = {39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)}, pages = {36:1--36:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-222-8}, ISSN = {1868-8969}, year = {2022}, volume = {219}, editor = {Berenbrink, Petra and Monmege, Benjamin}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2022.36}, URN = {urn:nbn:de:0030-drops-158464}, doi = {10.4230/LIPIcs.STACS.2022.36}, annote = {Keywords: connected edge sets, cutwidth, parameterized algorithms, colorings, counting modulo p} }
Published in: LIPIcs, Volume 214, 16th International Symposium on Parameterized and Exact Computation (IPEC 2021)
Hans L. Bodlaender, Carla Groenland, and Céline M. F. Swennenhuis. Parameterized Complexities of Dominating and Independent Set Reconfiguration. In 16th International Symposium on Parameterized and Exact Computation (IPEC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 214, pp. 9:1-9:16, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{bodlaender_et_al:LIPIcs.IPEC.2021.9, author = {Bodlaender, Hans L. and Groenland, Carla and Swennenhuis, C\'{e}line M. F.}, title = {{Parameterized Complexities of Dominating and Independent Set Reconfiguration}}, booktitle = {16th International Symposium on Parameterized and Exact Computation (IPEC 2021)}, pages = {9:1--9:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-216-7}, ISSN = {1868-8969}, year = {2021}, volume = {214}, editor = {Golovach, Petr A. and Zehavi, Meirav}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2021.9}, URN = {urn:nbn:de:0030-drops-153920}, doi = {10.4230/LIPIcs.IPEC.2021.9}, annote = {Keywords: Parameterized complexity, independent set reconfiguration, dominating set reconfiguration, W-hierarchy, XL, XNL, XNLP} }
Published in: LIPIcs, Volume 209, 35th International Symposium on Distributed Computing (DISC 2021)
Marthe Bonamy, Linda Cook, Carla Groenland, and Alexandra Wesolek. A Tight Local Algorithm for the Minimum Dominating Set Problem in Outerplanar Graphs. In 35th International Symposium on Distributed Computing (DISC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 209, pp. 13:1-13:18, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{bonamy_et_al:LIPIcs.DISC.2021.13, author = {Bonamy, Marthe and Cook, Linda and Groenland, Carla and Wesolek, Alexandra}, title = {{A Tight Local Algorithm for the Minimum Dominating Set Problem in Outerplanar Graphs}}, booktitle = {35th International Symposium on Distributed Computing (DISC 2021)}, pages = {13:1--13:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-210-5}, ISSN = {1868-8969}, year = {2021}, volume = {209}, editor = {Gilbert, Seth}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2021.13}, URN = {urn:nbn:de:0030-drops-148159}, doi = {10.4230/LIPIcs.DISC.2021.13}, annote = {Keywords: Outerplanar graphs, dominating set, LOCAL model, constant-factor approximation algorithm} }
Published in: LIPIcs, Volume 204, 29th Annual European Symposium on Algorithms (ESA 2021)
Michał Dębski, Marta Piecyk, and Paweł Rzążewski. Faster 3-Coloring of Small-Diameter Graphs. In 29th Annual European Symposium on Algorithms (ESA 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 204, pp. 37:1-37:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{debski_et_al:LIPIcs.ESA.2021.37, author = {D\k{e}bski, Micha{\l} and Piecyk, Marta and Rz\k{a}\.{z}ewski, Pawe{\l}}, title = {{Faster 3-Coloring of Small-Diameter Graphs}}, booktitle = {29th Annual European Symposium on Algorithms (ESA 2021)}, pages = {37:1--37:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-204-4}, ISSN = {1868-8969}, year = {2021}, volume = {204}, editor = {Mutzel, Petra and Pagh, Rasmus 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.2021.37}, URN = {urn:nbn:de:0030-drops-146181}, doi = {10.4230/LIPIcs.ESA.2021.37}, annote = {Keywords: 3-coloring, fine-grained complexity, subexponential-time algorithm, diameter} }
Feedback for Dagstuhl Publishing