LIPIcs, Volume 80
ICALP 2017, July 10-14, 2017, Warsaw, Poland
Editors: Ioannis Chatzigiannakis, Piotr Indyk, Fabian Kuhn, and Anca Muscholl
Published in: Dagstuhl Reports, Volume 13, Issue 2 (2023)
Martin Farach-Colton, Fabian Daniel Kuhn, Ronitt Rubinfeld, and Przemysław Uznański. From Big Data Theory to Big Data Practice (Dagstuhl Seminar 23071). In Dagstuhl Reports, Volume 13, Issue 2, pp. 33-46, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@Article{farachcolton_et_al:DagRep.13.2.33, author = {Farach-Colton, Martin and Kuhn, Fabian Daniel and Rubinfeld, Ronitt and Uzna\'{n}ski, Przemys{\l}aw}, title = {{From Big Data Theory to Big Data Practice (Dagstuhl Seminar 23071)}}, pages = {33--46}, journal = {Dagstuhl Reports}, ISSN = {2192-5283}, year = {2023}, volume = {13}, number = {2}, editor = {Farach-Colton, Martin and Kuhn, Fabian Daniel and Rubinfeld, Ronitt and Uzna\'{n}ski, Przemys{\l}aw}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/DagRep.13.2.33}, URN = {urn:nbn:de:0030-drops-191809}, doi = {10.4230/DagRep.13.2.33}, annote = {Keywords: external memory, local algorithms, sublinear algorithms} }
Published in: LIPIcs, Volume 281, 37th International Symposium on Distributed Computing (DISC 2023)
Alkida Balliu, Sebastian Brandt, Fabian Kuhn, Dennis Olivetti, and Gustav Schmid. On the Node-Averaged Complexity of Locally Checkable Problems on Trees. In 37th International Symposium on Distributed Computing (DISC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 281, pp. 7:1-7:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{balliu_et_al:LIPIcs.DISC.2023.7, author = {Balliu, Alkida and Brandt, Sebastian and Kuhn, Fabian and Olivetti, Dennis and Schmid, Gustav}, title = {{On the Node-Averaged Complexity of Locally Checkable Problems on Trees}}, booktitle = {37th International Symposium on Distributed Computing (DISC 2023)}, pages = {7:1--7:21}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-301-0}, ISSN = {1868-8969}, year = {2023}, volume = {281}, editor = {Oshman, Rotem}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2023.7}, URN = {urn:nbn:de:0030-drops-191330}, doi = {10.4230/LIPIcs.DISC.2023.7}, annote = {Keywords: distributed graph algorithms, locally checkable labelings, node-averaged complexity, trees} }
Published in: LIPIcs, Volume 281, 37th International Symposium on Distributed Computing (DISC 2023)
Mélanie Cambus, Fabian Kuhn, Shreyas Pai, and Jara Uitto. Time and Space Optimal Massively Parallel Algorithm for the 2-Ruling Set Problem. In 37th International Symposium on Distributed Computing (DISC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 281, pp. 11:1-11:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{cambus_et_al:LIPIcs.DISC.2023.11, author = {Cambus, M\'{e}lanie and Kuhn, Fabian and Pai, Shreyas and Uitto, Jara}, title = {{Time and Space Optimal Massively Parallel Algorithm for the 2-Ruling Set Problem}}, booktitle = {37th International Symposium on Distributed Computing (DISC 2023)}, pages = {11:1--11:12}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-301-0}, ISSN = {1868-8969}, year = {2023}, volume = {281}, editor = {Oshman, Rotem}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2023.11}, URN = {urn:nbn:de:0030-drops-191378}, doi = {10.4230/LIPIcs.DISC.2023.11}, annote = {Keywords: Ruling Sets, Parallel Algorithms, Congested Clique, Massively Parallel Computing, Semi-Streaming} }
Published in: LIPIcs, Volume 281, 37th International Symposium on Distributed Computing (DISC 2023)
Marc Fuchs and Fabian Kuhn. List Defective Colorings: Distributed Algorithms and Applications. In 37th International Symposium on Distributed Computing (DISC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 281, pp. 22:1-22:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{fuchs_et_al:LIPIcs.DISC.2023.22, author = {Fuchs, Marc and Kuhn, Fabian}, title = {{List Defective Colorings: Distributed Algorithms and Applications}}, booktitle = {37th International Symposium on Distributed Computing (DISC 2023)}, pages = {22:1--22:23}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-301-0}, ISSN = {1868-8969}, year = {2023}, volume = {281}, editor = {Oshman, Rotem}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2023.22}, URN = {urn:nbn:de:0030-drops-191484}, doi = {10.4230/LIPIcs.DISC.2023.22}, annote = {Keywords: distributed coloring, list coloring, defective coloring} }
Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)
Amirreza Akbari, Navid Eslami, Henrik Lievonen, Darya Melnyk, Joona Särkijärvi, and Jukka Suomela. Locality in Online, Dynamic, Sequential, and Distributed Graph Algorithms. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 10:1-10:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{akbari_et_al:LIPIcs.ICALP.2023.10, author = {Akbari, Amirreza and Eslami, Navid and Lievonen, Henrik and Melnyk, Darya and S\"{a}rkij\"{a}rvi, Joona and Suomela, Jukka}, title = {{Locality in Online, Dynamic, Sequential, and Distributed Graph Algorithms}}, booktitle = {50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)}, pages = {10:1--10: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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.10}, URN = {urn:nbn:de:0030-drops-180627}, doi = {10.4230/LIPIcs.ICALP.2023.10}, annote = {Keywords: Online computation, spatial advice, distributed algorithms, computational complexity} }
Published in: LIPIcs, Volume 246, 36th International Symposium on Distributed Computing (DISC 2022)
Fabian Kuhn and Philipp Schneider. Routing Schemes and Distance Oracles in the Hybrid Model. In 36th International Symposium on Distributed Computing (DISC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 246, pp. 28:1-28:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{kuhn_et_al:LIPIcs.DISC.2022.28, author = {Kuhn, Fabian and Schneider, Philipp}, title = {{Routing Schemes and Distance Oracles in the Hybrid Model}}, booktitle = {36th International Symposium on Distributed Computing (DISC 2022)}, pages = {28:1--28:22}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-255-6}, ISSN = {1868-8969}, year = {2022}, volume = {246}, editor = {Scheideler, Christian}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2022.28}, URN = {urn:nbn:de:0030-drops-172198}, doi = {10.4230/LIPIcs.DISC.2022.28}, annote = {Keywords: Distributed Computing, Graph Algorithms, Complexity Analysis} }
Published in: LIPIcs, Volume 219, 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)
Fabian Kuhn. Deterministic Distributed Symmetry Breaking at the Example of Distributed Graph Coloring (Invited Talk). In 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 219, p. 3:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{kuhn:LIPIcs.STACS.2022.3, author = {Kuhn, Fabian}, title = {{Deterministic Distributed Symmetry Breaking at the Example of Distributed Graph Coloring}}, booktitle = {39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)}, pages = {3:1--3:1}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2022.3}, URN = {urn:nbn:de:0030-drops-158131}, doi = {10.4230/LIPIcs.STACS.2022.3}, annote = {Keywords: distributed graph algorithms, derandomization, distributed coloring} }
Published in: LIPIcs, Volume 217, 25th International Conference on Principles of Distributed Systems (OPODIS 2021)
Sam Coy, Artur Czumaj, Michael Feldmann, Kristian Hinnenthal, Fabian Kuhn, Christian Scheideler, Philipp Schneider, and Martijn Struijs. Near-Shortest Path Routing in Hybrid Communication Networks. In 25th International Conference on Principles of Distributed Systems (OPODIS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 217, pp. 11:1-11:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{coy_et_al:LIPIcs.OPODIS.2021.11, author = {Coy, Sam and Czumaj, Artur and Feldmann, Michael and Hinnenthal, Kristian and Kuhn, Fabian and Scheideler, Christian and Schneider, Philipp and Struijs, Martijn}, title = {{Near-Shortest Path Routing in Hybrid Communication Networks}}, booktitle = {25th International Conference on Principles of Distributed Systems (OPODIS 2021)}, pages = {11:1--11:23}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-219-8}, ISSN = {1868-8969}, year = {2022}, volume = {217}, editor = {Bramas, Quentin and Gramoli, Vincent and Milani, Alessia}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2021.11}, URN = {urn:nbn:de:0030-drops-157863}, doi = {10.4230/LIPIcs.OPODIS.2021.11}, annote = {Keywords: Hybrid networks, overlay networks} }
Published in: LIPIcs, Volume 217, 25th International Conference on Principles of Distributed Systems (OPODIS 2021)
Salwa Faour, Marc Fuchs, and Fabian Kuhn. Distributed CONGEST Approximation of Weighted Vertex Covers and Matchings. In 25th International Conference on Principles of Distributed Systems (OPODIS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 217, pp. 17:1-17:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{faour_et_al:LIPIcs.OPODIS.2021.17, author = {Faour, Salwa and Fuchs, Marc and Kuhn, Fabian}, title = {{Distributed CONGEST Approximation of Weighted Vertex Covers and Matchings}}, booktitle = {25th International Conference on Principles of Distributed Systems (OPODIS 2021)}, pages = {17:1--17:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-219-8}, ISSN = {1868-8969}, year = {2022}, volume = {217}, editor = {Bramas, Quentin and Gramoli, Vincent and Milani, Alessia}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2021.17}, URN = {urn:nbn:de:0030-drops-157928}, doi = {10.4230/LIPIcs.OPODIS.2021.17}, annote = {Keywords: distributed graph algorithms, minimum weighted vertex cover, maximum weighted matching, distributed optimization, CONGEST model} }
Published in: LIPIcs, Volume 217, 25th International Conference on Principles of Distributed Systems (OPODIS 2021)
Alkida Balliu, Fabian Kuhn, and Dennis Olivetti. Improved Distributed Fractional Coloring Algorithms. In 25th International Conference on Principles of Distributed Systems (OPODIS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 217, pp. 18:1-18:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{balliu_et_al:LIPIcs.OPODIS.2021.18, author = {Balliu, Alkida and Kuhn, Fabian and Olivetti, Dennis}, title = {{Improved Distributed Fractional Coloring Algorithms}}, booktitle = {25th International Conference on Principles of Distributed Systems (OPODIS 2021)}, pages = {18:1--18:23}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-219-8}, ISSN = {1868-8969}, year = {2022}, volume = {217}, editor = {Bramas, Quentin and Gramoli, Vincent and Milani, Alessia}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2021.18}, URN = {urn:nbn:de:0030-drops-157935}, doi = {10.4230/LIPIcs.OPODIS.2021.18}, annote = {Keywords: distributed graph algorithms, distributed coloring, locality, fractional coloring} }
Published in: LIPIcs, Volume 217, 25th International Conference on Principles of Distributed Systems (OPODIS 2021)
Nicolas Bousquet, Laurent Feuilloley, Marc Heinrich, and Mikaël Rabie. Distributed Recoloring of Interval and Chordal Graphs. In 25th International Conference on Principles of Distributed Systems (OPODIS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 217, pp. 19:1-19:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{bousquet_et_al:LIPIcs.OPODIS.2021.19, author = {Bousquet, Nicolas and Feuilloley, Laurent and Heinrich, Marc and Rabie, Mika\"{e}l}, title = {{Distributed Recoloring of Interval and Chordal Graphs}}, booktitle = {25th International Conference on Principles of Distributed Systems (OPODIS 2021)}, pages = {19:1--19:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-219-8}, ISSN = {1868-8969}, year = {2022}, volume = {217}, editor = {Bramas, Quentin and Gramoli, Vincent and Milani, Alessia}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2021.19}, URN = {urn:nbn:de:0030-drops-157941}, doi = {10.4230/LIPIcs.OPODIS.2021.19}, annote = {Keywords: Distributed coloring, distributed recoloring, interval graphs, chordal graphs, intersection graphs} }
Published in: LIPIcs, Volume 187, 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)
Keren Censor-Hillel, Dean Leitersdorf, and Volodymyr Polosukhin. Distance Computations in the Hybrid Network Model via Oracle Simulations. In 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 187, pp. 21:1-21:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{censorhillel_et_al:LIPIcs.STACS.2021.21, author = {Censor-Hillel, Keren and Leitersdorf, Dean and Polosukhin, Volodymyr}, title = {{Distance Computations in the Hybrid Network Model via Oracle Simulations}}, booktitle = {38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)}, pages = {21:1--21:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-180-1}, ISSN = {1868-8969}, year = {2021}, volume = {187}, editor = {Bl\"{a}ser, Markus and Monmege, Benjamin}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2021.21}, URN = {urn:nbn:de:0030-drops-136663}, doi = {10.4230/LIPIcs.STACS.2021.21}, annote = {Keywords: Distributed graph algorithms, Hybrid network model, Distance computations} }
Published in: LIPIcs, Volume 184, 24th International Conference on Principles of Distributed Systems (OPODIS 2020)
Salwa Faour and Fabian Kuhn. Approximating Bipartite Minimum Vertex Cover in the CONGEST Model. In 24th International Conference on Principles of Distributed Systems (OPODIS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 184, pp. 29:1-29:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{faour_et_al:LIPIcs.OPODIS.2020.29, author = {Faour, Salwa and Kuhn, Fabian}, title = {{Approximating Bipartite Minimum Vertex Cover in the CONGEST Model}}, booktitle = {24th International Conference on Principles of Distributed Systems (OPODIS 2020)}, pages = {29:1--29:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-176-4}, ISSN = {1868-8969}, year = {2021}, volume = {184}, editor = {Bramas, Quentin and Oshman, Rotem and Romano, Paolo}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2020.29}, URN = {urn:nbn:de:0030-drops-135149}, doi = {10.4230/LIPIcs.OPODIS.2020.29}, annote = {Keywords: distributed vertex cover, distributed graph algorithms, distributed optimization, bipartite vertex cover} }
Published in: LIPIcs, Volume 179, 34th International Symposium on Distributed Computing (DISC 2020)
Mohamad Ahmadi and Fabian Kuhn. Distributed Maximum Matching Verification in CONGEST. In 34th International Symposium on Distributed Computing (DISC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 179, pp. 37:1-37:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{ahmadi_et_al:LIPIcs.DISC.2020.37, author = {Ahmadi, Mohamad and Kuhn, Fabian}, title = {{Distributed Maximum Matching Verification in CONGEST}}, booktitle = {34th International Symposium on Distributed Computing (DISC 2020)}, pages = {37:1--37:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-168-9}, ISSN = {1868-8969}, year = {2020}, volume = {179}, editor = {Attiya, Hagit}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2020.37}, URN = {urn:nbn:de:0030-drops-131151}, doi = {10.4230/LIPIcs.DISC.2020.37}, annote = {Keywords: distributed matching, distributed graph algorithms, augmenting paths} }
Feedback for Dagstuhl Publishing