LIPIcs, Volume 227
SWAT 2022, June 27-29, 2022, Tórshavn, Faroe Islands
Editors: Artur Czumaj and Qin Xin
LIPIcs, Volume 168
ICALP 2020, July 8-11, 2020, Saarbrücken, Germany (Virtual Conference)
Editors: Artur Czumaj, Anuj Dawar, and Emanuela Merelli
Published in: LIPIcs, Volume 275, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)
Yuval Filmus, Itai Leigh, Artur Riazanov, and Dmitry Sokolov. Sampling and Certifying Symmetric Functions. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 275, pp. 36:1-36:21, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{filmus_et_al:LIPIcs.APPROX/RANDOM.2023.36, author = {Filmus, Yuval and Leigh, Itai and Riazanov, Artur and Sokolov, Dmitry}, title = {{Sampling and Certifying Symmetric Functions}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)}, pages = {36:1--36:21}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-296-9}, ISSN = {1868-8969}, year = {2023}, volume = {275}, editor = {Megow, Nicole and Smith, Adam}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2023.36}, URN = {urn:nbn:de:0030-drops-188611}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2023.36}, annote = {Keywords: sampling, lower bounds, robust sunflowers, decision trees, switching networks} }
Published in: LIPIcs, Volume 272, 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)
Artur Czumaj. Modern Parallel Algorithms (Invited Talk). In 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 272, pp. 3:1-3:2, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{czumaj:LIPIcs.MFCS.2023.3, author = {Czumaj, Artur}, title = {{Modern Parallel Algorithms}}, booktitle = {48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)}, pages = {3:1--3:2}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-292-1}, ISSN = {1868-8969}, year = {2023}, volume = {272}, editor = {Leroux, J\'{e}r\^{o}me and Lombardy, Sylvain and Peleg, David}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2023.3}, URN = {urn:nbn:de:0030-drops-185378}, doi = {10.4230/LIPIcs.MFCS.2023.3}, annote = {Keywords: Distributed computing, parallel computing} }
Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)
Sam Coy, Artur Czumaj, Peter Davies, and Gopinath Mishra. Optimal (Degree+1)-Coloring in Congested Clique. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 46:1-46:20, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{coy_et_al:LIPIcs.ICALP.2023.46, author = {Coy, Sam and Czumaj, Artur and Davies, Peter and Mishra, Gopinath}, title = {{Optimal (Degree+1)-Coloring in Congested Clique}}, booktitle = {50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)}, pages = {46:1--46: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.46}, URN = {urn:nbn:de:0030-drops-180987}, doi = {10.4230/LIPIcs.ICALP.2023.46}, annote = {Keywords: Distributed computing, graph coloring, parallel computing} }
Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)
Artur Czumaj, Shaofeng H.-C. Jiang, Robert Krauthgamer, and Pavel Veselý. Streaming Algorithms for Geometric Steiner Forest. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 47:1-47:20, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{czumaj_et_al:LIPIcs.ICALP.2022.47, author = {Czumaj, Artur and Jiang, Shaofeng H.-C. and Krauthgamer, Robert and Vesel\'{y}, Pavel}, title = {{Streaming Algorithms for Geometric Steiner Forest}}, booktitle = {49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)}, pages = {47:1--47:20}, 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.47}, URN = {urn:nbn:de:0030-drops-163880}, doi = {10.4230/LIPIcs.ICALP.2022.47}, annote = {Keywords: Steiner forest, streaming, sublinear algorithms, dynamic programming} }
Published in: LIPIcs, Volume 227, 18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022)
Artur Czumaj and Qin Xin. LIPIcs, Volume 227, SWAT 2022, Complete Volume. In 18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 227, pp. 1-558, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@Proceedings{czumaj_et_al:LIPIcs.SWAT.2022, title = {{LIPIcs, Volume 227, SWAT 2022, Complete Volume}}, booktitle = {18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022)}, pages = {1--558}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-236-5}, ISSN = {1868-8969}, year = {2022}, volume = {227}, editor = {Czumaj, Artur and Xin, Qin}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2022}, URN = {urn:nbn:de:0030-drops-161599}, doi = {10.4230/LIPIcs.SWAT.2022}, annote = {Keywords: LIPIcs, Volume 227, SWAT 2022, Complete Volume} }
Published in: LIPIcs, Volume 227, 18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022)
Artur Czumaj and Qin Xin. Front Matter, Table of Contents, Preface, Conference Organization. In 18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 227, pp. 0:i-0:x, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{czumaj_et_al:LIPIcs.SWAT.2022.0, author = {Czumaj, Artur and Xin, Qin}, title = {{Front Matter, Table of Contents, Preface, Conference Organization}}, booktitle = {18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022)}, pages = {0:i--0:x}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-236-5}, ISSN = {1868-8969}, year = {2022}, volume = {227}, editor = {Czumaj, Artur and Xin, Qin}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2022.0}, URN = {urn:nbn:de:0030-drops-161602}, doi = {10.4230/LIPIcs.SWAT.2022.0}, annote = {Keywords: Front Matter, Table of Contents, Preface, Conference Organization} }
Published in: LIPIcs, Volume 227, 18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022)
Amotz Bar-Noy, Toni Böhnlein, David Peleg, and Dror Rawitz. On Realizing a Single Degree Sequence by a Bipartite Graph (Invited Paper). In 18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 227, pp. 1:1-1:17, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{barnoy_et_al:LIPIcs.SWAT.2022.1, author = {Bar-Noy, Amotz and B\"{o}hnlein, Toni and Peleg, David and Rawitz, Dror}, title = {{On Realizing a Single Degree Sequence by a Bipartite Graph}}, booktitle = {18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022)}, pages = {1:1--1:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-236-5}, ISSN = {1868-8969}, year = {2022}, volume = {227}, editor = {Czumaj, Artur and Xin, Qin}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2022.1}, URN = {urn:nbn:de:0030-drops-161618}, doi = {10.4230/LIPIcs.SWAT.2022.1}, annote = {Keywords: Degree Sequences, Graph Realization, Bipartite Graphs, Graphic Sequences, Bigraphic Sequences, Multigraph Realization} }
Published in: LIPIcs, Volume 227, 18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022)
Leszek Gąsieniec and Grzegorz Stachowiak. Time, Clocks and Efficiency of Population Protocols (Invited Paper). In 18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 227, pp. 2:1-2:2, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{gasieniec_et_al:LIPIcs.SWAT.2022.2, author = {G\k{a}sieniec, Leszek and Stachowiak, Grzegorz}, title = {{Time, Clocks and Efficiency of Population Protocols}}, booktitle = {18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022)}, pages = {2:1--2:2}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-236-5}, ISSN = {1868-8969}, year = {2022}, volume = {227}, editor = {Czumaj, Artur and Xin, Qin}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2022.2}, URN = {urn:nbn:de:0030-drops-161624}, doi = {10.4230/LIPIcs.SWAT.2022.2}, annote = {Keywords: Population protocols, phase clocks, oscillators, parallel time and efficiency} }
Published in: LIPIcs, Volume 227, 18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022)
Mikkel Thorup. Reconstructing the Tree of Life (Fitting Distances by Tree Metrics) (Invited Paper). In 18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 227, pp. 3:1-3:2, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{thorup:LIPIcs.SWAT.2022.3, author = {Thorup, Mikkel}, title = {{Reconstructing the Tree of Life (Fitting Distances by Tree Metrics)}}, booktitle = {18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022)}, pages = {3:1--3:2}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-236-5}, ISSN = {1868-8969}, year = {2022}, volume = {227}, editor = {Czumaj, Artur and Xin, Qin}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2022.3}, URN = {urn:nbn:de:0030-drops-161631}, doi = {10.4230/LIPIcs.SWAT.2022.3}, annote = {Keywords: Numerical taxonomy, computational phylogenetics, hierarchical clustering} }
Published in: LIPIcs, Volume 227, 18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022)
Hugo A. Akitaya, Erik D. Demaine, Matias Korman, Irina Kostitsyna, Irene Parada, Willem Sonke, Bettina Speckmann, Ryuhei Uehara, and Jules Wulms. Compacting Squares: Input-Sensitive In-Place Reconfiguration of Sliding Squares. In 18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 227, pp. 4:1-4:19, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{a.akitaya_et_al:LIPIcs.SWAT.2022.4, author = {A. Akitaya, Hugo and Demaine, Erik D. and Korman, Matias and Kostitsyna, Irina and Parada, Irene and Sonke, Willem and Speckmann, Bettina and Uehara, Ryuhei and Wulms, Jules}, title = {{Compacting Squares: Input-Sensitive In-Place Reconfiguration of Sliding Squares}}, booktitle = {18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022)}, pages = {4:1--4:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-236-5}, ISSN = {1868-8969}, year = {2022}, volume = {227}, editor = {Czumaj, Artur and Xin, Qin}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2022.4}, URN = {urn:nbn:de:0030-drops-161644}, doi = {10.4230/LIPIcs.SWAT.2022.4}, annote = {Keywords: Sliding cubes, Reconfiguration, Modular robots, NP-hardness} }
Published in: LIPIcs, Volume 227, 18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022)
David Adjiashvili, Felix Hommelsheim, Moritz Mühlenthaler, and Oliver Schaudt. Fault-Tolerant Edge-Disjoint s-t Paths - Beyond Uniform Faults. In 18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 227, pp. 5:1-5:19, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{adjiashvili_et_al:LIPIcs.SWAT.2022.5, author = {Adjiashvili, David and Hommelsheim, Felix and M\"{u}hlenthaler, Moritz and Schaudt, Oliver}, title = {{Fault-Tolerant Edge-Disjoint s-t Paths - Beyond Uniform Faults}}, booktitle = {18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022)}, pages = {5:1--5:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-236-5}, ISSN = {1868-8969}, year = {2022}, volume = {227}, editor = {Czumaj, Artur and Xin, Qin}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2022.5}, URN = {urn:nbn:de:0030-drops-161659}, doi = {10.4230/LIPIcs.SWAT.2022.5}, annote = {Keywords: graph algorithms, network design, fault tolerance, approximation algorithms} }
Published in: LIPIcs, Volume 227, 18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022)
Pankaj K. Agarwal, Sharath Raghvendra, Pouyan Shirzadian, and Rachita Sowle. An Improved ε-Approximation Algorithm for Geometric Bipartite Matching. In 18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 227, pp. 6:1-6:20, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{agarwal_et_al:LIPIcs.SWAT.2022.6, author = {Agarwal, Pankaj K. and Raghvendra, Sharath and Shirzadian, Pouyan and Sowle, Rachita}, title = {{An Improved \epsilon-Approximation Algorithm for Geometric Bipartite Matching}}, booktitle = {18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022)}, pages = {6:1--6:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-236-5}, ISSN = {1868-8969}, year = {2022}, volume = {227}, editor = {Czumaj, Artur and Xin, Qin}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2022.6}, URN = {urn:nbn:de:0030-drops-161660}, doi = {10.4230/LIPIcs.SWAT.2022.6}, annote = {Keywords: Euclidean bipartite matching, approximation algorithms, primal dual method} }
Published in: LIPIcs, Volume 227, 18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022)
Safwa Ameer, Matt Gibson-Lopez, Erik Krohn, and Qing Wang. On the Visibility Graphs of Pseudo-Polygons: Recognition and Reconstruction. In 18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 227, pp. 7:1-7:13, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{ameer_et_al:LIPIcs.SWAT.2022.7, author = {Ameer, Safwa and Gibson-Lopez, Matt and Krohn, Erik and Wang, Qing}, title = {{On the Visibility Graphs of Pseudo-Polygons: Recognition and Reconstruction}}, booktitle = {18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022)}, pages = {7:1--7:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-236-5}, ISSN = {1868-8969}, year = {2022}, volume = {227}, editor = {Czumaj, Artur and Xin, Qin}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2022.7}, URN = {urn:nbn:de:0030-drops-161673}, doi = {10.4230/LIPIcs.SWAT.2022.7}, annote = {Keywords: Pseudo-Polygons, Visibility Graph Recognition, Visibility Graph Reconstruction} }
Feedback for Dagstuhl Publishing