LIPIcs, Volume 244
ESA 2022, September 5-9, 2022, Berlin/Potsdam, Germany
Editors: Shiri Chechik, Gonzalo Navarro, Eva Rotenberg, and Grzegorz Herman
Published in: Dagstuhl Reports, Volume 12, Issue 11 (2023)
Aaron Bernstein, Shiri Chechik, Sebastian Forster, Tsvi Kopelowitz, Yasamin Nazari, and Nicole Wein. Dynamic Graph Algorithms (Dagstuhl Seminar 22461). In Dagstuhl Reports, Volume 12, Issue 11, pp. 45-65, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@Article{bernstein_et_al:DagRep.12.11.45, author = {Bernstein, Aaron and Chechik, Shiri and Forster, Sebastian and Kopelowitz, Tsvi and Nazari, Yasamin and Wein, Nicole}, title = {{Dynamic Graph Algorithms (Dagstuhl Seminar 22461)}}, pages = {45--65}, journal = {Dagstuhl Reports}, ISSN = {2192-5283}, year = {2023}, volume = {12}, number = {11}, editor = {Bernstein, Aaron and Chechik, Shiri and Forster, Sebastian and Kopelowitz, Tsvi and Nazari, Yasamin and Wein, Nicole}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/DagRep.12.11.45}, URN = {urn:nbn:de:0030-drops-178354}, doi = {10.4230/DagRep.12.11.45}, annote = {Keywords: dynamic graphs, graph algorithms} }
Published in: LIPIcs, Volume 244, 30th Annual European Symposium on Algorithms (ESA 2022)
30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 1-1406, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@Proceedings{chechik_et_al:LIPIcs.ESA.2022, title = {{LIPIcs, Volume 244, ESA 2022, Complete Volume}}, booktitle = {30th Annual European Symposium on Algorithms (ESA 2022)}, pages = {1--1406}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2022}, URN = {urn:nbn:de:0030-drops-169374}, doi = {10.4230/LIPIcs.ESA.2022}, annote = {Keywords: LIPIcs, Volume 244, ESA 2022, Complete Volume} }
Published in: LIPIcs, Volume 244, 30th Annual European Symposium on Algorithms (ESA 2022)
30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 0:i-0:xxii, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{chechik_et_al:LIPIcs.ESA.2022.0, author = {Chechik, Shiri and Navarro, Gonzalo and Rotenberg, Eva and Herman, Grzegorz}, title = {{Front Matter, Table of Contents, Preface, Conference Organization}}, booktitle = {30th Annual European Symposium on Algorithms (ESA 2022)}, pages = {0:i--0:xxii}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2022.0}, URN = {urn:nbn:de:0030-drops-169382}, doi = {10.4230/LIPIcs.ESA.2022.0}, annote = {Keywords: Front Matter, Table of Contents, Preface, Conference Organization} }
Published in: LIPIcs, Volume 244, 30th Annual European Symposium on Algorithms (ESA 2022)
Faisal N. Abu-Khzam, Henning Fernau, Benjamin Gras, Mathieu Liedloff, and Kevin Mann. Enumerating Minimal Connected Dominating Sets. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 1:1-1:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{abukhzam_et_al:LIPIcs.ESA.2022.1, author = {Abu-Khzam, Faisal N. and Fernau, Henning and Gras, Benjamin and Liedloff, Mathieu and Mann, Kevin}, title = {{Enumerating Minimal Connected Dominating Sets}}, booktitle = {30th Annual European Symposium on Algorithms (ESA 2022)}, pages = {1:1--1: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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2022.1}, URN = {urn:nbn:de:0030-drops-169390}, doi = {10.4230/LIPIcs.ESA.2022.1}, annote = {Keywords: enumeration problems, connected domination, degenerate graphs} }
Published in: LIPIcs, Volume 244, 30th Annual European Symposium on Algorithms (ESA 2022)
Raghavendra Addanki, Andrew McGregor, and Cameron Musco. Non-Adaptive Edge Counting and Sampling via Bipartite Independent Set Queries. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 2:1-2:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{addanki_et_al:LIPIcs.ESA.2022.2, author = {Addanki, Raghavendra and McGregor, Andrew and Musco, Cameron}, title = {{Non-Adaptive Edge Counting and Sampling via Bipartite Independent Set Queries}}, booktitle = {30th Annual European Symposium on Algorithms (ESA 2022)}, pages = {2:1--2:16}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2022.2}, URN = {urn:nbn:de:0030-drops-169400}, doi = {10.4230/LIPIcs.ESA.2022.2}, annote = {Keywords: sublinear graph algorithms, bipartite independent set queries, edge sampling and counting, graph connectivity, query adaptivity} }
Published in: LIPIcs, Volume 244, 30th Annual European Symposium on Algorithms (ESA 2022)
Oswin Aichholzer, Erik D. Demaine, Matias Korman, Anna Lubiw, Jayson Lynch, Zuzana Masárová, Mikhail Rudoy, Virginia Vassilevska Williams, and Nicole Wein. Hardness of Token Swapping on Trees. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 3:1-3:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{aichholzer_et_al:LIPIcs.ESA.2022.3, author = {Aichholzer, Oswin and Demaine, Erik D. and Korman, Matias and Lubiw, Anna and Lynch, Jayson and Mas\'{a}rov\'{a}, Zuzana and Rudoy, Mikhail and Vassilevska Williams, Virginia and Wein, Nicole}, title = {{Hardness of Token Swapping on Trees}}, booktitle = {30th Annual European Symposium on Algorithms (ESA 2022)}, pages = {3:1--3: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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2022.3}, URN = {urn:nbn:de:0030-drops-169413}, doi = {10.4230/LIPIcs.ESA.2022.3}, annote = {Keywords: Sorting, Token swapping, Trees, NP-hard, Approximation} }
Published in: LIPIcs, Volume 244, 30th Annual European Symposium on Algorithms (ESA 2022)
Susanne Albers and Sebastian Schubert. Tight Bounds for Online Matching in Bounded-Degree Graphs with Vertex Capacities. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 4:1-4:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{albers_et_al:LIPIcs.ESA.2022.4, author = {Albers, Susanne and Schubert, Sebastian}, title = {{Tight Bounds for Online Matching in Bounded-Degree Graphs with Vertex Capacities}}, booktitle = {30th Annual European Symposium on Algorithms (ESA 2022)}, pages = {4:1--4:16}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2022.4}, URN = {urn:nbn:de:0030-drops-169420}, doi = {10.4230/LIPIcs.ESA.2022.4}, annote = {Keywords: online algorithms, deterministic algorithms, primal-dual analysis, b-matching, bounded-degree graph, variable vertex capacities, unweighted matching, vertex-weighted matching} }
Published in: LIPIcs, Volume 244, 30th Annual European Symposium on Algorithms (ESA 2022)
Henk Alkema, Mark de Berg, Morteza Monemizadeh, and Leonidas Theocharous. TSP in a Simple Polygon. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 5:1-5:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{alkema_et_al:LIPIcs.ESA.2022.5, author = {Alkema, Henk and de Berg, Mark and Monemizadeh, Morteza and Theocharous, Leonidas}, title = {{TSP in a Simple Polygon}}, booktitle = {30th Annual European Symposium on Algorithms (ESA 2022)}, pages = {5:1--5: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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2022.5}, URN = {urn:nbn:de:0030-drops-169434}, doi = {10.4230/LIPIcs.ESA.2022.5}, annote = {Keywords: Traveling Salesman Problem, Subexponential algorithms, TSP with obstacles} }
Published in: LIPIcs, Volume 244, 30th Annual European Symposium on Algorithms (ESA 2022)
Jonathan Allcock, Yassine Hamoudi, Antoine Joux, Felix Klingelhöfer, and Miklos Santha. Classical and Quantum Algorithms for Variants of Subset-Sum via Dynamic Programming. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 6:1-6:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{allcock_et_al:LIPIcs.ESA.2022.6, author = {Allcock, Jonathan and Hamoudi, Yassine and Joux, Antoine and Klingelh\"{o}fer, Felix and Santha, Miklos}, title = {{Classical and Quantum Algorithms for Variants of Subset-Sum via Dynamic Programming}}, booktitle = {30th Annual European Symposium on Algorithms (ESA 2022)}, pages = {6:1--6:18}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2022.6}, URN = {urn:nbn:de:0030-drops-169444}, doi = {10.4230/LIPIcs.ESA.2022.6}, annote = {Keywords: Quantum algorithm, classical algorithm, dynamic programming, representation technique, subset-sum, equal-sum, shifted-sum} }
Published in: LIPIcs, Volume 244, 30th Annual European Symposium on Algorithms (ESA 2022)
Georg Anegg, Laura Vargas Koch, and Rico Zenklusen. Techniques for Generalized Colorful k-Center Problems. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 7:1-7:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{anegg_et_al:LIPIcs.ESA.2022.7, author = {Anegg, Georg and Vargas Koch, Laura and Zenklusen, Rico}, title = {{Techniques for Generalized Colorful k-Center Problems}}, booktitle = {30th Annual European Symposium on Algorithms (ESA 2022)}, pages = {7:1--7: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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2022.7}, URN = {urn:nbn:de:0030-drops-169458}, doi = {10.4230/LIPIcs.ESA.2022.7}, annote = {Keywords: Approximation Algorithms, Fair Clustering, Colorful k-Center} }
Published in: LIPIcs, Volume 244, 30th Annual European Symposium on Algorithms (ESA 2022)
Mohammad Ansari, Mohammad Saneian, and Hamid Zarrabi-Zadeh. Simple Streaming Algorithms for Edge Coloring. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 8:1-8:4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{ansari_et_al:LIPIcs.ESA.2022.8, author = {Ansari, Mohammad and Saneian, Mohammad and Zarrabi-Zadeh, Hamid}, title = {{Simple Streaming Algorithms for Edge Coloring}}, booktitle = {30th Annual European Symposium on Algorithms (ESA 2022)}, pages = {8:1--8:4}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2022.8}, URN = {urn:nbn:de:0030-drops-169468}, doi = {10.4230/LIPIcs.ESA.2022.8}, annote = {Keywords: Edge coloring, streaming model, adversarial order} }
Published in: LIPIcs, Volume 244, 30th Annual European Symposium on Algorithms (ESA 2022)
Antonios Antoniadis, Mark de Berg, Sándor Kisfaludi-Bak, and Antonis Skarlatos. Computing Smallest Convex Intersecting Polygons. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 9:1-9:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{antoniadis_et_al:LIPIcs.ESA.2022.9, author = {Antoniadis, Antonios and de Berg, Mark and Kisfaludi-Bak, S\'{a}ndor and Skarlatos, Antonis}, title = {{Computing Smallest Convex Intersecting Polygons}}, booktitle = {30th Annual European Symposium on Algorithms (ESA 2022)}, pages = {9:1--9: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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2022.9}, URN = {urn:nbn:de:0030-drops-169470}, doi = {10.4230/LIPIcs.ESA.2022.9}, annote = {Keywords: convex hull, imprecise points, computational geometry} }
Published in: LIPIcs, Volume 244, 30th Annual European Symposium on Algorithms (ESA 2022)
Anna Arutyunova and Heiko Röglin. The Price of Hierarchical Clustering. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 10:1-10:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{arutyunova_et_al:LIPIcs.ESA.2022.10, author = {Arutyunova, Anna and R\"{o}glin, Heiko}, title = {{The Price of Hierarchical Clustering}}, booktitle = {30th Annual European Symposium on Algorithms (ESA 2022)}, pages = {10:1--10: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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2022.10}, URN = {urn:nbn:de:0030-drops-169487}, doi = {10.4230/LIPIcs.ESA.2022.10}, annote = {Keywords: Hierarchical Clustering, approximation Algorithms, k-center Problem} }
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-dev.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} }
Feedback for Dagstuhl Publishing