Published in: LIPIcs, Volume 286, 27th International Conference on Principles of Distributed Systems (OPODIS 2023)
Avinandan Das, Pierre Fraigniaud, and Adi Rosén. Distributed Partial Coloring via Gradual Rounding. In 27th International Conference on Principles of Distributed Systems (OPODIS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 286, pp. 30:1-30:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{das_et_al:LIPIcs.OPODIS.2023.30, author = {Das, Avinandan and Fraigniaud, Pierre and Ros\'{e}n, Adi}, title = {{Distributed Partial Coloring via Gradual Rounding}}, booktitle = {27th International Conference on Principles of Distributed Systems (OPODIS 2023)}, pages = {30:1--30:22}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-308-9}, ISSN = {1868-8969}, year = {2024}, volume = {286}, editor = {Bessani, Alysson and D\'{e}fago, Xavier and Nakamura, Junya and Wada, Koichi and Yamauchi, Yukiko}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2023.30}, URN = {urn:nbn:de:0030-drops-195205}, doi = {10.4230/LIPIcs.OPODIS.2023.30}, annote = {Keywords: Distributed graph coloring, partial coloring, weak coloring} }
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 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 257, 2nd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2023)
Swan Dubois, Laurent Feuilloley, Franck Petit, and Mikaël Rabie. When Should You Wait Before Updating? - Toward a Robustness Refinement. In 2nd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 257, pp. 7:1-7:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{dubois_et_al:LIPIcs.SAND.2023.7, author = {Dubois, Swan and Feuilloley, Laurent and Petit, Franck and Rabie, Mika\"{e}l}, title = {{When Should You Wait Before Updating? - Toward a Robustness Refinement}}, booktitle = {2nd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2023)}, pages = {7:1--7:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-275-4}, ISSN = {1868-8969}, year = {2023}, volume = {257}, editor = {Doty, David and Spirakis, Paul}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2023.7}, URN = {urn:nbn:de:0030-drops-179435}, doi = {10.4230/LIPIcs.SAND.2023.7}, annote = {Keywords: Robustness, dynamic network, temporal graphs, edge removal, connectivity, footprint, packing/covering problems, maximal independent set, maximal matching, minimum dominating set, perfect matching, NP-hardness} }
Published in: LIPIcs, Volume 246, 36th International Symposium on Distributed Computing (DISC 2022)
Alkida Balliu, Sebastian Brandt, Yi-Jun Chang, Dennis Olivetti, Jan Studený, and Jukka Suomela. Efficient Classification of Locally Checkable Problems in Regular Trees. In 36th International Symposium on Distributed Computing (DISC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 246, pp. 8:1-8:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{balliu_et_al:LIPIcs.DISC.2022.8, author = {Balliu, Alkida and Brandt, Sebastian and Chang, Yi-Jun and Olivetti, Dennis and Studen\'{y}, Jan and Suomela, Jukka}, title = {{Efficient Classification of Locally Checkable Problems in Regular Trees}}, booktitle = {36th International Symposium on Distributed Computing (DISC 2022)}, pages = {8:1--8:19}, 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.8}, URN = {urn:nbn:de:0030-drops-171993}, doi = {10.4230/LIPIcs.DISC.2022.8}, annote = {Keywords: locally checkable labeling, locality, distributed computational complexity} }
Published in: LIPIcs, Volume 246, 36th International Symposium on Distributed Computing (DISC 2022)
Alkida Balliu, Sebastian Brandt, Manuela Fischer, Rustam Latypov, Yannic Maus, Dennis Olivetti, and Jara Uitto. Exponential Speedup over Locality in MPC with Optimal Memory. In 36th International Symposium on Distributed Computing (DISC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 246, pp. 9:1-9:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{balliu_et_al:LIPIcs.DISC.2022.9, author = {Balliu, Alkida and Brandt, Sebastian and Fischer, Manuela and Latypov, Rustam and Maus, Yannic and Olivetti, Dennis and Uitto, Jara}, title = {{Exponential Speedup over Locality in MPC with Optimal Memory}}, booktitle = {36th International Symposium on Distributed Computing (DISC 2022)}, pages = {9:1--9:21}, 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.9}, URN = {urn:nbn:de:0030-drops-172003}, doi = {10.4230/LIPIcs.DISC.2022.9}, annote = {Keywords: Distributed computing, Locally checkable labeling problems, Trees, Massively Parallel Computation, Sublinear memory} }
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 209, 35th International Symposium on Distributed Computing (DISC 2021)
Alkida Balliu, Keren Censor-Hillel, Yannic Maus, Dennis Olivetti, and Jukka Suomela. Locally Checkable Labelings with Small Messages. In 35th International Symposium on Distributed Computing (DISC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 209, pp. 8:1-8:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{balliu_et_al:LIPIcs.DISC.2021.8, author = {Balliu, Alkida and Censor-Hillel, Keren and Maus, Yannic and Olivetti, Dennis and Suomela, Jukka}, title = {{Locally Checkable Labelings with Small Messages}}, booktitle = {35th International Symposium on Distributed Computing (DISC 2021)}, pages = {8:1--8:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-210-5}, ISSN = {1868-8969}, year = {2021}, volume = {209}, editor = {Gilbert, Seth}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2021.8}, URN = {urn:nbn:de:0030-drops-148109}, doi = {10.4230/LIPIcs.DISC.2021.8}, annote = {Keywords: distributed graph algorithms, CONGEST, locally checkable labelings} }
Published in: LIPIcs, Volume 179, 34th International Symposium on Distributed Computing (DISC 2020)
Alkida Balliu, Sebastian Brandt, Yuval Efron, Juho Hirvonen, Yannic Maus, Dennis Olivetti, and Jukka Suomela. Classification of Distributed Binary Labeling Problems. In 34th International Symposium on Distributed Computing (DISC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 179, pp. 17:1-17:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{balliu_et_al:LIPIcs.DISC.2020.17, author = {Balliu, Alkida and Brandt, Sebastian and Efron, Yuval and Hirvonen, Juho and Maus, Yannic and Olivetti, Dennis and Suomela, Jukka}, title = {{Classification of Distributed Binary Labeling Problems}}, booktitle = {34th International Symposium on Distributed Computing (DISC 2020)}, pages = {17:1--17:17}, 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.17}, URN = {urn:nbn:de:0030-drops-130957}, doi = {10.4230/LIPIcs.DISC.2020.17}, annote = {Keywords: LOCAL model, graph problems, locally checkable labeling problems, distributed computational complexity} }
Published in: LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)
Keren Censor-Hillel and Mikaël Rabie. Distributed Reconfiguration of Maximal Independent Sets. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 135:1-135:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{censorhillel_et_al:LIPIcs.ICALP.2019.135, author = {Censor-Hillel, Keren and Rabie, Mika\"{e}l}, title = {{Distributed Reconfiguration of Maximal Independent Sets}}, booktitle = {46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)}, pages = {135:1--135:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-109-2}, ISSN = {1868-8969}, year = {2019}, volume = {132}, editor = {Baier, Christel and Chatzigiannakis, Ioannis and Flocchini, Paola and Leonardi, Stefano}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.135}, URN = {urn:nbn:de:0030-drops-107111}, doi = {10.4230/LIPIcs.ICALP.2019.135}, annote = {Keywords: distributed graph algorithms, reconfiguration, maximal independent set} }
Published in: LIPIcs, Volume 121, 32nd International Symposium on Distributed Computing (DISC 2018)
Alkida Balliu, Sebastian Brandt, Dennis Olivetti, and Jukka Suomela. Almost Global Problems in the LOCAL Model. In 32nd International Symposium on Distributed Computing (DISC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 121, pp. 9:1-9:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{balliu_et_al:LIPIcs.DISC.2018.9, author = {Balliu, Alkida and Brandt, Sebastian and Olivetti, Dennis and Suomela, Jukka}, title = {{Almost Global Problems in the LOCAL Model}}, booktitle = {32nd International Symposium on Distributed Computing (DISC 2018)}, pages = {9:1--9:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-092-7}, ISSN = {1868-8969}, year = {2018}, volume = {121}, editor = {Schmid, Ulrich and Widder, Josef}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2018.9}, URN = {urn:nbn:de:0030-drops-97982}, doi = {10.4230/LIPIcs.DISC.2018.9}, annote = {Keywords: Distributed complexity theory, locally checkable labellings, LOCAL model} }
Published in: LIPIcs, Volume 91, 31st International Symposium on Distributed Computing (DISC 2017)
Guy Even, Orr Fischer, Pierre Fraigniaud, Tzlil Gonen, Reut Levi, Moti Medina, Pedro Montealegre, Dennis Olivetti, Rotem Oshman, Ivan Rapaport, and Ioan Todinca. Three Notes on Distributed Property Testing. In 31st International Symposium on Distributed Computing (DISC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 91, pp. 15:1-15:30, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{even_et_al:LIPIcs.DISC.2017.15, author = {Even, Guy and Fischer, Orr and Fraigniaud, Pierre and Gonen, Tzlil and Levi, Reut and Medina, Moti and Montealegre, Pedro and Olivetti, Dennis and Oshman, Rotem and Rapaport, Ivan and Todinca, Ioan}, title = {{Three Notes on Distributed Property Testing}}, booktitle = {31st International Symposium on Distributed Computing (DISC 2017)}, pages = {15:1--15:30}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-053-8}, ISSN = {1868-8969}, year = {2017}, volume = {91}, editor = {Richa, Andr\'{e}a}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2017.15}, URN = {urn:nbn:de:0030-drops-79847}, doi = {10.4230/LIPIcs.DISC.2017.15}, annote = {Keywords: Property testing, Property correcting, Distributed algorithms, CONGEST model} }
Published in: LIPIcs, Volume 66, 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)
Alkida Balliu, Gianlorenzo D'Angelo, Pierre Fraigniaud, and Dennis Olivetti. What Can Be Verified Locally?. In 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 66, pp. 8:1-8:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{balliu_et_al:LIPIcs.STACS.2017.8, author = {Balliu, Alkida and D'Angelo, Gianlorenzo and Fraigniaud, Pierre and Olivetti, Dennis}, title = {{What Can Be Verified Locally?}}, booktitle = {34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)}, pages = {8:1--8:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-028-6}, ISSN = {1868-8969}, year = {2017}, volume = {66}, editor = {Vollmer, Heribert and Vall\'{e}e, Brigitte}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2017.8}, URN = {urn:nbn:de:0030-drops-70253}, doi = {10.4230/LIPIcs.STACS.2017.8}, annote = {Keywords: Distributed Network Computing, Distributed Algorithm, Distributed Decision, Locality} }
Feedback for Dagstuhl Publishing