LIPIcs, Volume 214
IPEC 2021, September 8-10, 2021, Lisbon, Portugal
Editors: Petr A. Golovach and Meirav Zehavi
Published in: LIPIcs, Volume 325, 16th Innovations in Theoretical Computer Science Conference (ITCS 2025)
Fedor V. Fomin, Petr A. Golovach, Tanmay Inamdar, Saket Saurabh, and Meirav Zehavi. Parameterized Geometric Graph Modification with Disk Scaling. In 16th Innovations in Theoretical Computer Science Conference (ITCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 325, pp. 51:1-51:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)
@InProceedings{fomin_et_al:LIPIcs.ITCS.2025.51, author = {Fomin, Fedor V. and Golovach, Petr A. and Inamdar, Tanmay and Saurabh, Saket and Zehavi, Meirav}, title = {{Parameterized Geometric Graph Modification with Disk Scaling}}, booktitle = {16th Innovations in Theoretical Computer Science Conference (ITCS 2025)}, pages = {51:1--51:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-361-4}, ISSN = {1868-8969}, year = {2025}, volume = {325}, editor = {Meka, Raghu}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2025.51}, URN = {urn:nbn:de:0030-drops-226795}, doi = {10.4230/LIPIcs.ITCS.2025.51}, annote = {Keywords: parameterized algorithms, kernelization, spreading points, distant representatives, unit disk packing} }
Published in: LIPIcs, Volume 322, 35th International Symposium on Algorithms and Computation (ISAAC 2024)
Giordano Da Lozzo, Robert Ganian, Siddharth Gupta, Bojan Mohar, Sebastian Ordyniak, and Meirav Zehavi. Exact Algorithms for Clustered Planarity with Linear Saturators. In 35th International Symposium on Algorithms and Computation (ISAAC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 322, pp. 24:1-24:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{dalozzo_et_al:LIPIcs.ISAAC.2024.24, author = {Da Lozzo, Giordano and Ganian, Robert and Gupta, Siddharth and Mohar, Bojan and Ordyniak, Sebastian and Zehavi, Meirav}, title = {{Exact Algorithms for Clustered Planarity with Linear Saturators}}, booktitle = {35th International Symposium on Algorithms and Computation (ISAAC 2024)}, pages = {24:1--24:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-354-6}, ISSN = {1868-8969}, year = {2024}, volume = {322}, editor = {Mestre, Juli\'{a}n and Wirth, Anthony}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2024.24}, URN = {urn:nbn:de:0030-drops-221513}, doi = {10.4230/LIPIcs.ISAAC.2024.24}, annote = {Keywords: Clustered planarity, independent c-graphs, path saturation, graph drawing} }
Published in: LIPIcs, Volume 322, 35th International Symposium on Algorithms and Computation (ISAAC 2024)
Ashwin Jacob, Diptapriyo Majumdar, and Meirav Zehavi. A Polynomial Kernel for Deletion to the Scattered Class of Cliques and Trees. In 35th International Symposium on Algorithms and Computation (ISAAC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 322, pp. 41:1-41:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{jacob_et_al:LIPIcs.ISAAC.2024.41, author = {Jacob, Ashwin and Majumdar, Diptapriyo and Zehavi, Meirav}, title = {{A Polynomial Kernel for Deletion to the Scattered Class of Cliques and Trees}}, booktitle = {35th International Symposium on Algorithms and Computation (ISAAC 2024)}, pages = {41:1--41:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-354-6}, ISSN = {1868-8969}, year = {2024}, volume = {322}, editor = {Mestre, Juli\'{a}n and Wirth, Anthony}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2024.41}, URN = {urn:nbn:de:0030-drops-221687}, doi = {10.4230/LIPIcs.ISAAC.2024.41}, annote = {Keywords: Parameterized Complexity, Kernelization, Scattered Graph Classes, New Expansion Lemma, Cliques or Trees Vertex Deletion} }
Published in: LIPIcs, Volume 317, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)
Fedor V. Fomin, Petr A. Golovach, Tanmay Inamdar, Saket Saurabh, and Meirav Zehavi. Hybrid k-Clustering: Blending k-Median and k-Center. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 317, pp. 4:1-4:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{fomin_et_al:LIPIcs.APPROX/RANDOM.2024.4, author = {Fomin, Fedor V. and Golovach, Petr A. and Inamdar, Tanmay and Saurabh, Saket and Zehavi, Meirav}, title = {{Hybrid k-Clustering: Blending k-Median and k-Center}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)}, pages = {4:1--4:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-348-5}, ISSN = {1868-8969}, year = {2024}, volume = {317}, editor = {Kumar, Amit and Ron-Zewi, Noga}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2024.4}, URN = {urn:nbn:de:0030-drops-209975}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2024.4}, annote = {Keywords: clustering, k-center, k-median, Euclidean space, fpt approximation} }
Published in: LIPIcs, Volume 317, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)
Daniel Lokshtanov, Fahad Panolan, Saket Saurabh, Jie Xue, and Meirav Zehavi. Bipartizing (Pseudo-)Disk Graphs: Approximation with a Ratio Better than 3. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 317, pp. 6:1-6:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{lokshtanov_et_al:LIPIcs.APPROX/RANDOM.2024.6, author = {Lokshtanov, Daniel and Panolan, Fahad and Saurabh, Saket and Xue, Jie and Zehavi, Meirav}, title = {{Bipartizing (Pseudo-)Disk Graphs: Approximation with a Ratio Better than 3}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)}, pages = {6:1--6:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-348-5}, ISSN = {1868-8969}, year = {2024}, volume = {317}, editor = {Kumar, Amit and Ron-Zewi, Noga}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2024.6}, URN = {urn:nbn:de:0030-drops-209990}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2024.6}, annote = {Keywords: bipartization, geometric intersection graphs, approximation algorithms} }
Published in: LIPIcs, Volume 293, 40th International Symposium on Computational Geometry (SoCG 2024)
Daniel Lokshtanov, Fahad Panolan, Saket Saurabh, Jie Xue, and Meirav Zehavi. A 1.9999-Approximation Algorithm for Vertex Cover on String Graphs. In 40th International Symposium on Computational Geometry (SoCG 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 293, pp. 72:1-72:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{lokshtanov_et_al:LIPIcs.SoCG.2024.72, author = {Lokshtanov, Daniel and Panolan, Fahad and Saurabh, Saket and Xue, Jie and Zehavi, Meirav}, title = {{A 1.9999-Approximation Algorithm for Vertex Cover on String Graphs}}, booktitle = {40th International Symposium on Computational Geometry (SoCG 2024)}, pages = {72:1--72:11}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-316-4}, ISSN = {1868-8969}, year = {2024}, volume = {293}, editor = {Mulzer, Wolfgang and Phillips, Jeff M.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2024.72}, URN = {urn:nbn:de:0030-drops-200174}, doi = {10.4230/LIPIcs.SoCG.2024.72}, annote = {Keywords: vertex cover, geometric intersection graphs, approximation algorithms} }
Published in: Dagstuhl Reports, Volume 13, Issue 7 (2024)
Karthik C. S., Parinya Chalermsook, Joachim Spoerhase, Meirav Zehavi, and Martin Herold. Parameterized Approximation: Algorithms and Hardness (Dagstuhl Seminar 23291). In Dagstuhl Reports, Volume 13, Issue 7, pp. 96-107, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@Article{c.s._et_al:DagRep.13.7.96, author = {C. S., Karthik and Chalermsook, Parinya and Spoerhase, Joachim and Zehavi, Meirav and Herold, Martin}, title = {{Parameterized Approximation: Algorithms and Hardness (Dagstuhl Seminar 23291)}}, pages = {96--107}, journal = {Dagstuhl Reports}, ISSN = {2192-5283}, year = {2024}, volume = {13}, number = {7}, editor = {C. S., Karthik and Chalermsook, Parinya and Spoerhase, Joachim and Zehavi, Meirav and Herold, Martin}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagRep.13.7.96}, URN = {urn:nbn:de:0030-drops-197764}, doi = {10.4230/DagRep.13.7.96}, annote = {Keywords: approximation algorithms, Hardness of approximation, Parameterized algorithms} }
Published in: LIPIcs, Volume 287, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024)
Daniel Lokshtanov, Pranabendu Misra, Saket Saurabh, and Meirav Zehavi. Kernelization of Counting Problems. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 287, pp. 77:1-77:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{lokshtanov_et_al:LIPIcs.ITCS.2024.77, author = {Lokshtanov, Daniel and Misra, Pranabendu and Saurabh, Saket and Zehavi, Meirav}, title = {{Kernelization of Counting Problems}}, booktitle = {15th Innovations in Theoretical Computer Science Conference (ITCS 2024)}, pages = {77:1--77:23}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-309-6}, ISSN = {1868-8969}, year = {2024}, volume = {287}, editor = {Guruswami, Venkatesan}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2024.77}, URN = {urn:nbn:de:0030-drops-196059}, doi = {10.4230/LIPIcs.ITCS.2024.77}, annote = {Keywords: Kernelization, Counting Problems} }
Published in: LIPIcs, Volume 285, 18th International Symposium on Parameterized and Exact Computation (IPEC 2023)
Juhi Chaudhary, Harmender Gahlawat, Michal Włodarczyk, and Meirav Zehavi. Kernels for the Disjoint Paths Problem on Subclasses of Chordal Graphs. In 18th International Symposium on Parameterized and Exact Computation (IPEC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 285, pp. 10:1-10:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{chaudhary_et_al:LIPIcs.IPEC.2023.10, author = {Chaudhary, Juhi and Gahlawat, Harmender and W{\l}odarczyk, Michal and Zehavi, Meirav}, title = {{Kernels for the Disjoint Paths Problem on Subclasses of Chordal Graphs}}, booktitle = {18th International Symposium on Parameterized and Exact Computation (IPEC 2023)}, pages = {10:1--10:22}, 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.10}, URN = {urn:nbn:de:0030-drops-194296}, doi = {10.4230/LIPIcs.IPEC.2023.10}, annote = {Keywords: Kernelization, Parameterized Complexity, Vertex-Disjoint Paths Problem, Edge-Disjoint Paths Problem} }
Published in: LIPIcs, Volume 285, 18th International Symposium on Parameterized and Exact Computation (IPEC 2023)
Siddharth Gupta, Guy Sa'ar, and Meirav Zehavi. Collective Graph Exploration Parameterized by Vertex Cover. In 18th International Symposium on Parameterized and Exact Computation (IPEC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 285, pp. 22:1-22:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{gupta_et_al:LIPIcs.IPEC.2023.22, author = {Gupta, Siddharth and Sa'ar, Guy and Zehavi, Meirav}, title = {{Collective Graph Exploration Parameterized by Vertex Cover}}, booktitle = {18th International Symposium on Parameterized and Exact Computation (IPEC 2023)}, pages = {22:1--22:18}, 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.22}, URN = {urn:nbn:de:0030-drops-194413}, doi = {10.4230/LIPIcs.IPEC.2023.22}, annote = {Keywords: Collective Graph Exploration, Parameterized Complexity, Approximation Algorithm, Vertex Cover, Treedepth} }
Published in: LIPIcs, Volume 285, 18th International Symposium on Parameterized and Exact Computation (IPEC 2023)
Siddharth Gupta, Guy Sa'ar, and Meirav Zehavi. Drawn Tree Decomposition: New Approach for Graph Drawing Problems. In 18th International Symposium on Parameterized and Exact Computation (IPEC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 285, pp. 23:1-23:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{gupta_et_al:LIPIcs.IPEC.2023.23, author = {Gupta, Siddharth and Sa'ar, Guy and Zehavi, Meirav}, title = {{Drawn Tree Decomposition: New Approach for Graph Drawing Problems}}, booktitle = {18th International Symposium on Parameterized and Exact Computation (IPEC 2023)}, pages = {23:1--23:22}, 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.23}, URN = {urn:nbn:de:0030-drops-194424}, doi = {10.4230/LIPIcs.IPEC.2023.23}, annote = {Keywords: Graph Drawing, Parameterized Complexity, Tree decomposition} }
Published in: LIPIcs, Volume 285, 18th International Symposium on Parameterized and Exact Computation (IPEC 2023)
Ioannis Koutis, Michał Włodarczyk, and Meirav Zehavi. Sidestepping Barriers for Dominating Set in Parameterized Complexity. In 18th International Symposium on Parameterized and Exact Computation (IPEC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 285, pp. 31:1-31:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{koutis_et_al:LIPIcs.IPEC.2023.31, author = {Koutis, Ioannis and W{\l}odarczyk, Micha{\l} and Zehavi, Meirav}, title = {{Sidestepping Barriers for Dominating Set in Parameterized Complexity}}, booktitle = {18th International Symposium on Parameterized and Exact Computation (IPEC 2023)}, pages = {31:1--31: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.31}, URN = {urn:nbn:de:0030-drops-194506}, doi = {10.4230/LIPIcs.IPEC.2023.31}, annote = {Keywords: Dominating Set, Parameterized Complexity, Approximation Algorithms} }
Published in: LIPIcs, Volume 284, 43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2023)
Harmender Gahlawat and Meirav Zehavi. Parameterized Complexity of Incomplete Connected Fair Division. In 43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 284, pp. 14:1-14:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{gahlawat_et_al:LIPIcs.FSTTCS.2023.14, author = {Gahlawat, Harmender and Zehavi, Meirav}, title = {{Parameterized Complexity of Incomplete Connected Fair Division}}, booktitle = {43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2023)}, pages = {14:1--14:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-304-1}, ISSN = {1868-8969}, year = {2023}, volume = {284}, editor = {Bouyer, Patricia and Srinivasan, Srikanth}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2023.14}, URN = {urn:nbn:de:0030-drops-193877}, doi = {10.4230/LIPIcs.FSTTCS.2023.14}, annote = {Keywords: Fair Division, Kernelization, Connected Fair Allocation, 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} }
Feedback for Dagstuhl Publishing