Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Augusto Modanese and Yuichi Yoshida. Testing Spreading Behavior in Networks with Arbitrary Topologies. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 112:1-112:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{modanese_et_al:LIPIcs.ICALP.2024.112, author = {Modanese, Augusto and Yoshida, Yuichi}, title = {{Testing Spreading Behavior in Networks with Arbitrary Topologies}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {112:1--112:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-322-5}, ISSN = {1868-8969}, year = {2024}, volume = {297}, editor = {Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.112}, URN = {urn:nbn:de:0030-drops-202554}, doi = {10.4230/LIPIcs.ICALP.2024.112}, annote = {Keywords: Property testing, bootstrap percolation, local phenomena, expander graphs} }
Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)
Petra Berenbrink, Lukas Hintze, Hamed Hosseinpour, Dominik Kaaser, and Malin Rau. Dynamic Averaging Load Balancing on Arbitrary Graphs. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 18:1-18:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{berenbrink_et_al:LIPIcs.ICALP.2023.18, author = {Berenbrink, Petra and Hintze, Lukas and Hosseinpour, Hamed and Kaaser, Dominik and Rau, Malin}, title = {{Dynamic Averaging Load Balancing on Arbitrary Graphs}}, booktitle = {50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)}, pages = {18:1--18:18}, 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.18}, URN = {urn:nbn:de:0030-drops-180707}, doi = {10.4230/LIPIcs.ICALP.2023.18}, annote = {Keywords: Dynamic Load Balancing, Distributed Computing, Randomized Algorithms, Drift Analysis} }
Published in: LIPIcs, Volume 253, 26th International Conference on Principles of Distributed Systems (OPODIS 2022)
Petra Berenbrink, Amin Coja-Oghlan, Oliver Gebhard, Max Hahn-Klimroth, Dominik Kaaser, and Malin Rau. On the Hierarchy of Distributed Majority Protocols. In 26th International Conference on Principles of Distributed Systems (OPODIS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 253, pp. 23:1-23:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{berenbrink_et_al:LIPIcs.OPODIS.2022.23, author = {Berenbrink, Petra and Coja-Oghlan, Amin and Gebhard, Oliver and Hahn-Klimroth, Max and Kaaser, Dominik and Rau, Malin}, title = {{On the Hierarchy of Distributed Majority Protocols}}, booktitle = {26th International Conference on Principles of Distributed Systems (OPODIS 2022)}, pages = {23:1--23:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-265-5}, ISSN = {1868-8969}, year = {2023}, volume = {253}, editor = {Hillel, Eshcar and Palmieri, Roberto and Rivi\`{e}re, Etienne}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2022.23}, URN = {urn:nbn:de:0030-drops-176434}, doi = {10.4230/LIPIcs.OPODIS.2022.23}, annote = {Keywords: Consensus, Majority, Hierarchy, Stochastic Dominance, Population Protocols, Gossip Model, Strassen’s Theorem} }
Published in: LIPIcs, Volume 221, 1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022)
Petra Berenbrink, Felix Biermeier, Christopher Hahn, and Dominik Kaaser. Loosely-Stabilizing Phase Clocks and The Adaptive Majority Problem. In 1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 221, pp. 7:1-7:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{berenbrink_et_al:LIPIcs.SAND.2022.7, author = {Berenbrink, Petra and Biermeier, Felix and Hahn, Christopher and Kaaser, Dominik}, title = {{Loosely-Stabilizing Phase Clocks and The Adaptive Majority Problem}}, booktitle = {1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022)}, pages = {7:1--7:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-224-2}, ISSN = {1868-8969}, year = {2022}, volume = {221}, editor = {Aspnes, James and Michail, Othon}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2022.7}, URN = {urn:nbn:de:0030-drops-159493}, doi = {10.4230/LIPIcs.SAND.2022.7}, annote = {Keywords: Population Protocols, Phase Clocks, Loose Self-stabilization, Clock Synchronization, Majority, Adaptive} }
Published in: LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)
Christoph Damerius, Dominik Kaaser, Peter Kling, and Florian Schneider. On Greedily Packing Anchored Rectangles. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 61:1-61:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{damerius_et_al:LIPIcs.ICALP.2021.61, author = {Damerius, Christoph and Kaaser, Dominik and Kling, Peter and Schneider, Florian}, title = {{On Greedily Packing Anchored Rectangles}}, booktitle = {48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)}, pages = {61:1--61:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-195-5}, ISSN = {1868-8969}, year = {2021}, volume = {198}, editor = {Bansal, Nikhil and Merelli, Emanuela and Worrell, James}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.61}, URN = {urn:nbn:de:0030-drops-141306}, doi = {10.4230/LIPIcs.ICALP.2021.61}, annote = {Keywords: lower-left anchored rectangle packing, greedy algorithm, charging scheme} }
Published in: LIPIcs, Volume 173, 28th Annual European Symposium on Algorithms (ESA 2020)
Petra Berenbrink, David Hammer, Dominik Kaaser, Ulrich Meyer, Manuel Penschuck, and Hung Tran. Simulating Population Protocols in Sub-Constant Time per Interaction. In 28th Annual European Symposium on Algorithms (ESA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 173, pp. 16:1-16:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{berenbrink_et_al:LIPIcs.ESA.2020.16, author = {Berenbrink, Petra and Hammer, David and Kaaser, Dominik and Meyer, Ulrich and Penschuck, Manuel and Tran, Hung}, title = {{Simulating Population Protocols in Sub-Constant Time per Interaction}}, booktitle = {28th Annual European Symposium on Algorithms (ESA 2020)}, pages = {16:1--16:22}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-162-7}, ISSN = {1868-8969}, year = {2020}, volume = {173}, editor = {Grandoni, Fabrizio and Herman, Grzegorz and Sanders, Peter}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2020.16}, URN = {urn:nbn:de:0030-drops-128827}, doi = {10.4230/LIPIcs.ESA.2020.16}, annote = {Keywords: Population Protocols, Simulation, Random Sampling, Dynamic Alias Table} }
Published in: LIPIcs, Volume 144, 27th Annual European Symposium on Algorithms (ESA 2019)
Antonios Antoniadis, Felix Biermeier, Andrés Cristi, Christoph Damerius, Ruben Hoeksma, Dominik Kaaser, Peter Kling, and Lukas Nölke. On the Complexity of Anchored Rectangle Packing. In 27th Annual European Symposium on Algorithms (ESA 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 144, pp. 8:1-8:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{antoniadis_et_al:LIPIcs.ESA.2019.8, author = {Antoniadis, Antonios and Biermeier, Felix and Cristi, Andr\'{e}s and Damerius, Christoph and Hoeksma, Ruben and Kaaser, Dominik and Kling, Peter and N\"{o}lke, Lukas}, title = {{On the Complexity of Anchored Rectangle Packing}}, booktitle = {27th Annual European Symposium on Algorithms (ESA 2019)}, pages = {8:1--8:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-124-5}, ISSN = {1868-8969}, year = {2019}, volume = {144}, editor = {Bender, Michael A. and Svensson, Ola and Herman, Grzegorz}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2019.8}, URN = {urn:nbn:de:0030-drops-111297}, doi = {10.4230/LIPIcs.ESA.2019.8}, annote = {Keywords: anchored rectangle, rectangle packing, resource augmentation, PTAS, NP, hardness} }
Published in: LIPIcs, Volume 121, 32nd International Symposium on Distributed Computing (DISC 2018)
Petra Berenbrink, Robert Elsässer, Tom Friedetzky, Dominik Kaaser, Peter Kling, and Tomasz Radzik. A Population Protocol for Exact Majority with O(log5/3 n) Stabilization Time and Theta(log n) States. In 32nd International Symposium on Distributed Computing (DISC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 121, pp. 10:1-10:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{berenbrink_et_al:LIPIcs.DISC.2018.10, author = {Berenbrink, Petra and Els\"{a}sser, Robert and Friedetzky, Tom and Kaaser, Dominik and Kling, Peter and Radzik, Tomasz}, title = {{A Population Protocol for Exact Majority with O(log5/3 n) Stabilization Time and Theta(log n) States}}, booktitle = {32nd International Symposium on Distributed Computing (DISC 2018)}, pages = {10:1--10:18}, 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.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2018.10}, URN = {urn:nbn:de:0030-drops-97999}, doi = {10.4230/LIPIcs.DISC.2018.10}, annote = {Keywords: Population Protocols, Randomized Algorithms, Majority} }
Published in: OASIcs, Volume 61, 1st Symposium on Simplicity in Algorithms (SOSA 2018)
Petra Berenbrink, Dominik Kaaser, Peter Kling, and Lena Otterbach. Simple and Efficient Leader Election. In 1st Symposium on Simplicity in Algorithms (SOSA 2018). Open Access Series in Informatics (OASIcs), Volume 61, pp. 9:1-9:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{berenbrink_et_al:OASIcs.SOSA.2018.9, author = {Berenbrink, Petra and Kaaser, Dominik and Kling, Peter and Otterbach, Lena}, title = {{Simple and Efficient Leader Election}}, booktitle = {1st Symposium on Simplicity in Algorithms (SOSA 2018)}, pages = {9:1--9:11}, series = {Open Access Series in Informatics (OASIcs)}, ISBN = {978-3-95977-064-4}, ISSN = {2190-6807}, year = {2018}, volume = {61}, editor = {Seidel, Raimund}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.SOSA.2018.9}, URN = {urn:nbn:de:0030-drops-83029}, doi = {10.4230/OASIcs.SOSA.2018.9}, annote = {Keywords: population protocols, leader election, distributed, randomized} }
Published in: LIPIcs, Volume 58, 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)
Dominik Kaaser, Frederik Mallmann-Trenn, and Emanuele Natale. On the Voting Time of the Deterministic Majority Process. In 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 58, pp. 55:1-55:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
@InProceedings{kaaser_et_al:LIPIcs.MFCS.2016.55, author = {Kaaser, Dominik and Mallmann-Trenn, Frederik and Natale, Emanuele}, title = {{On the Voting Time of the Deterministic Majority Process}}, booktitle = {41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)}, pages = {55:1--55:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-016-3}, ISSN = {1868-8969}, year = {2016}, volume = {58}, editor = {Faliszewski, Piotr and Muscholl, Anca and Niedermeier, Rolf}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2016.55}, URN = {urn:nbn:de:0030-drops-64675}, doi = {10.4230/LIPIcs.MFCS.2016.55}, annote = {Keywords: distributed voting, majority rule} }
Feedback for Dagstuhl Publishing