LIPIcs, Volume 241
MFCS 2022, August 22-26, 2022, Vienna, Austria
Editors: Stefan Szeider, Robert Ganian, and Alexandra Silva
Published in: LIPIcs, Volume 285, 18th International Symposium on Parameterized and Exact Computation (IPEC 2023)
Eduard Eiben, Robert Ganian, Iyad Kanj, Sebastian Ordyniak, and Stefan Szeider. From Data Completion to Problems on Hypercubes: A Parameterized Analysis of the Independent Set Problem. In 18th International Symposium on Parameterized and Exact Computation (IPEC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 285, pp. 16:1-16:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{eiben_et_al:LIPIcs.IPEC.2023.16, author = {Eiben, Eduard and Ganian, Robert and Kanj, Iyad and Ordyniak, Sebastian and Szeider, Stefan}, title = {{From Data Completion to Problems on Hypercubes: A Parameterized Analysis of the Independent Set Problem}}, booktitle = {18th International Symposium on Parameterized and Exact Computation (IPEC 2023)}, pages = {16:1--16:14}, 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.16}, URN = {urn:nbn:de:0030-drops-194357}, doi = {10.4230/LIPIcs.IPEC.2023.16}, annote = {Keywords: Independent Set, Powers of Hypercubes, Diversity, Parameterized Complexity, Incomplete Data} }
Published in: LIPIcs, Volume 285, 18th International Symposium on Parameterized and Exact Computation (IPEC 2023)
Robert Ganian, Liana Khazaliya, and Kirill Simonov. Consistency Checking Problems: A Gateway to Parameterized Sample Complexity. In 18th International Symposium on Parameterized and Exact Computation (IPEC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 285, pp. 18:1-18:17, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{ganian_et_al:LIPIcs.IPEC.2023.18, author = {Ganian, Robert and Khazaliya, Liana and Simonov, Kirill}, title = {{Consistency Checking Problems: A Gateway to Parameterized Sample Complexity}}, booktitle = {18th International Symposium on Parameterized and Exact Computation (IPEC 2023)}, pages = {18:1--18:17}, 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.18}, URN = {urn:nbn:de:0030-drops-194374}, doi = {10.4230/LIPIcs.IPEC.2023.18}, annote = {Keywords: consistency checking, sample complexity, fixed-parameter tractability} }
Published in: Dagstuhl Reports, Volume 13, Issue 4 (2023)
Robert Ganian, Fabrizio Montecchiani, Martin Nöllenburg, Meirav Zehavi, and Liana Khazaliya. New Frontiers of Parameterized Complexity in Graph Drawing (Dagstuhl Seminar 23162). In Dagstuhl Reports, Volume 13, Issue 4, pp. 58-97, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@Article{ganian_et_al:DagRep.13.4.58, author = {Ganian, Robert and Montecchiani, Fabrizio and N\"{o}llenburg, Martin and Zehavi, Meirav and Khazaliya, Liana}, title = {{New Frontiers of Parameterized Complexity in Graph Drawing (Dagstuhl Seminar 23162)}}, pages = {58--97}, journal = {Dagstuhl Reports}, ISSN = {2192-5283}, year = {2023}, volume = {13}, number = {4}, editor = {Ganian, Robert and Montecchiani, Fabrizio and N\"{o}llenburg, Martin and Zehavi, Meirav and Khazaliya, Liana}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagRep.13.4.58}, URN = {urn:nbn:de:0030-drops-192393}, doi = {10.4230/DagRep.13.4.58}, annote = {Keywords: algorithm design, computational geometry, graph drawing, parameterized complexity} }
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 258, 39th International Symposium on Computational Geometry (SoCG 2023)
Sujoy Bhore, Robert Ganian, Liana Khazaliya, Fabrizio Montecchiani, and Martin Nöllenburg. Extending Orthogonal Planar Graph Drawings Is Fixed-Parameter Tractable. In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 18:1-18:16, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{bhore_et_al:LIPIcs.SoCG.2023.18, author = {Bhore, Sujoy and Ganian, Robert and Khazaliya, Liana and Montecchiani, Fabrizio and N\"{o}llenburg, Martin}, title = {{Extending Orthogonal Planar Graph Drawings Is Fixed-Parameter Tractable}}, booktitle = {39th International Symposium on Computational Geometry (SoCG 2023)}, pages = {18:1--18:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-273-0}, ISSN = {1868-8969}, year = {2023}, volume = {258}, editor = {Chambers, Erin W. and Gudmundsson, Joachim}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2023.18}, URN = {urn:nbn:de:0030-drops-178689}, doi = {10.4230/LIPIcs.SoCG.2023.18}, annote = {Keywords: orthogonal drawings, bend minimization, extension problems, parameterized complexity} }
Published in: LIPIcs, Volume 258, 39th International Symposium on Computational Geometry (SoCG 2023)
Eduard Eiben, Robert Ganian, and Iyad Kanj. The Parameterized Complexity of Coordinated Motion Planning. In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 28:1-28:16, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{eiben_et_al:LIPIcs.SoCG.2023.28, author = {Eiben, Eduard and Ganian, Robert and Kanj, Iyad}, title = {{The Parameterized Complexity of Coordinated Motion Planning}}, booktitle = {39th International Symposium on Computational Geometry (SoCG 2023)}, pages = {28:1--28:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-273-0}, ISSN = {1868-8969}, year = {2023}, volume = {258}, editor = {Chambers, Erin W. and Gudmundsson, Joachim}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2023.28}, URN = {urn:nbn:de:0030-drops-178784}, doi = {10.4230/LIPIcs.SoCG.2023.28}, annote = {Keywords: coordinated motion planning, multi-agent path finding, parameterized complexity, disjoint paths on grids} }
Published in: LIPIcs, Volume 248, 33rd International Symposium on Algorithms and Computation (ISAAC 2022)
Michael A. Bekos, Giordano Da Lozzo, Petr Hliněný, and Michael Kaufmann. Graph Product Structure for h-Framed Graphs. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 23:1-23:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{bekos_et_al:LIPIcs.ISAAC.2022.23, author = {Bekos, Michael A. and Da Lozzo, Giordano and Hlin\v{e}n\'{y}, Petr and Kaufmann, Michael}, title = {{Graph Product Structure for h-Framed Graphs}}, booktitle = {33rd International Symposium on Algorithms and Computation (ISAAC 2022)}, pages = {23:1--23:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-258-7}, ISSN = {1868-8969}, year = {2022}, volume = {248}, editor = {Bae, Sang Won and Park, Heejin}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2022.23}, URN = {urn:nbn:de:0030-drops-173086}, doi = {10.4230/LIPIcs.ISAAC.2022.23}, annote = {Keywords: Graph product structure theory, h-framed graphs, k-map graphs, queue number, twin-width} }
Published in: LIPIcs, Volume 249, 17th International Symposium on Parameterized and Exact Computation (IPEC 2022)
Robert Ganian and Viktoriia Korchemna. Slim Tree-Cut Width. In 17th International Symposium on Parameterized and Exact Computation (IPEC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 249, pp. 15:1-15:18, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{ganian_et_al:LIPIcs.IPEC.2022.15, author = {Ganian, Robert and Korchemna, Viktoriia}, title = {{Slim Tree-Cut Width}}, booktitle = {17th International Symposium on Parameterized and Exact Computation (IPEC 2022)}, pages = {15:1--15: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.15}, URN = {urn:nbn:de:0030-drops-173714}, doi = {10.4230/LIPIcs.IPEC.2022.15}, annote = {Keywords: tree-cut width, structural parameters, graph immersions} }
Published in: LIPIcs, Volume 244, 30th Annual European Symposium on Algorithms (ESA 2022)
Martin Balko, Steven Chaplick, Robert Ganian, Siddharth Gupta, Michael Hoffmann, Pavel Valtr, and Alexander Wolff. Bounding and Computing Obstacle Numbers of Graphs. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 11:1-11:13, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{balko_et_al:LIPIcs.ESA.2022.11, author = {Balko, Martin and Chaplick, Steven and Ganian, Robert and Gupta, Siddharth and Hoffmann, Michael and Valtr, Pavel and Wolff, Alexander}, title = {{Bounding and Computing Obstacle Numbers of Graphs}}, booktitle = {30th Annual European Symposium on Algorithms (ESA 2022)}, pages = {11:1--11:13}, 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.11}, URN = {urn:nbn:de:0030-drops-169495}, doi = {10.4230/LIPIcs.ESA.2022.11}, annote = {Keywords: Obstacle representation, Obstacle number, Visibility, NP-hardness, FPT} }
Published in: LIPIcs, Volume 244, 30th Annual European Symposium on Algorithms (ESA 2022)
Eduard Eiben, Robert Ganian, Iyad Kanj, Sebastian Ordyniak, and Stefan Szeider. Finding a Cluster in Incomplete Data. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 47:1-47:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{eiben_et_al:LIPIcs.ESA.2022.47, author = {Eiben, Eduard and Ganian, Robert and Kanj, Iyad and Ordyniak, Sebastian and Szeider, Stefan}, title = {{Finding a Cluster in Incomplete Data}}, booktitle = {30th Annual European Symposium on Algorithms (ESA 2022)}, pages = {47:1--47: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.47}, URN = {urn:nbn:de:0030-drops-169858}, doi = {10.4230/LIPIcs.ESA.2022.47}, annote = {Keywords: Parameterized complexity, incomplete data, clustering} }
Published in: LIPIcs, Volume 241, 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)
Stefan Szeider, Robert Ganian, and Alexandra Silva. LIPIcs, Volume 241, MFCS 2022, Complete Volume. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 1-1236, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@Proceedings{szeider_et_al:LIPIcs.MFCS.2022, title = {{LIPIcs, Volume 241, MFCS 2022, Complete Volume}}, booktitle = {47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)}, pages = {1--1236}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-256-3}, ISSN = {1868-8969}, year = {2022}, volume = {241}, editor = {Szeider, Stefan and Ganian, Robert and Silva, Alexandra}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022}, URN = {urn:nbn:de:0030-drops-167975}, doi = {10.4230/LIPIcs.MFCS.2022}, annote = {Keywords: LIPIcs, Volume 241, MFCS 2022, Complete Volume} }
Published in: LIPIcs, Volume 241, 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)
Stefan Szeider, Robert Ganian, and Alexandra Silva. Front Matter, Table of Contents, Preface, Conference Organization. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 0:i-0:xviii, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{szeider_et_al:LIPIcs.MFCS.2022.0, author = {Szeider, Stefan and Ganian, Robert and Silva, Alexandra}, title = {{Front Matter, Table of Contents, Preface, Conference Organization}}, booktitle = {47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)}, pages = {0:i--0:xviii}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-256-3}, ISSN = {1868-8969}, year = {2022}, volume = {241}, editor = {Szeider, Stefan and Ganian, Robert and Silva, Alexandra}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022.0}, URN = {urn:nbn:de:0030-drops-167981}, doi = {10.4230/LIPIcs.MFCS.2022.0}, annote = {Keywords: Front Matter, Table of Contents, Preface, Conference Organization} }
Published in: LIPIcs, Volume 241, 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)
Fedor V. Fomin, Petr A. Golovach, Danil Sagunov, and Kirill Simonov. Long Cycles in Graphs: Extremal Combinatorics Meets Parameterized Algorithms (Invited Talk). In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 1:1-1:4, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{fomin_et_al:LIPIcs.MFCS.2022.1, author = {Fomin, Fedor V. and Golovach, Petr A. and Sagunov, Danil and Simonov, Kirill}, title = {{Long Cycles in Graphs: Extremal Combinatorics Meets Parameterized Algorithms}}, booktitle = {47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)}, pages = {1:1--1:4}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-256-3}, ISSN = {1868-8969}, year = {2022}, volume = {241}, editor = {Szeider, Stefan and Ganian, Robert and Silva, Alexandra}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022.1}, URN = {urn:nbn:de:0030-drops-167999}, doi = {10.4230/LIPIcs.MFCS.2022.1}, annote = {Keywords: Longest path, longest cycle, fixed-parameter tractability, above guarantee parameterization, average degree, dense graph, Dirac theorem, Erd\H{o}s-Gallai theorem} }
Published in: LIPIcs, Volume 241, 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)
Monika Henzinger. Modern Dynamic Data Structures (Invited Talk). In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 2:1-2:2, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{henzinger:LIPIcs.MFCS.2022.2, author = {Henzinger, Monika}, title = {{Modern Dynamic Data Structures}}, booktitle = {47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)}, pages = {2:1--2:2}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-256-3}, ISSN = {1868-8969}, year = {2022}, volume = {241}, editor = {Szeider, Stefan and Ganian, Robert and Silva, Alexandra}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022.2}, URN = {urn:nbn:de:0030-drops-168009}, doi = {10.4230/LIPIcs.MFCS.2022.2}, annote = {Keywords: Differential privacy, data structures} }
Feedback for Dagstuhl Publishing