Distributed Algorithms for Fundamental Graph Problems (DiAloG)
This website collects all activity related to the research project "Distributed Algorithms for Fundamental Graph Problems (DiAloG)". The main objective in this project is to develop faster graph algorithms in the CONGEST model of distributed computing with provable correctness and running time guarantees.
Principal Investigator: Sebastian Forster
Host Institution: University of Salzburg
Funding Agency: Austrian Science Fund (FWF)
Project Number: P 32863-N
Duration: 03/2020 – 02/2024
Team Members
- Sebastian Forster, PI
- Elisabeth Riedl, administration
- Emilio Cruciani, postdoc
- Yasamin Nazari, postdoc
- Tijn de Vos, PhD student
- Anna Bolotina, MSc student
Former Team Members
- Judith Warter, administration
- Mara Grilnberger, BSc student
- Martin Grösbacher, BSc student
Publications
- The Laplacian Paradigm in the Broadcast Congested Clique
Sebastian Forster and Tijn de Vos
41st ACM Symposium on Principles of Distributed Computing (PODC), 2022
arXiv - A Framework for Distributed Quantum Queries in the CONGEST Model/em>
Joran van Apeldoorn and Tijn de Vos
41st ACM Symposium on Principles of Distributed Computing (PODC), 2022
arXiv - Faster Cut Sparsification of Weighted Graphs
Sebastian Forster and Tijn de Vos
49th EATCS International Colloquium on Automata, Languages, and Programming (ICALP), 2022
arXiv - Near-Optimal Decremental Hopsets with Applications
Jakub Lacki, Yasamin Nazari
49th EATCS International Colloquium on Automata, Languages, and Programming (ICALP), 2022
arXiv - Minor Sparsifiers and the Distributed Laplacian Paradigm
Sebastian Forster, Gramoz Goranci, Yang P. Liu, Richard Peng, Xiaorui Sun, and Mingquan Ye
62nd Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2022
arXiv - Vertex Fault-Tolerant Emulators
Greg Bodwin, Michael Dinitz, and Yasamin Nazari
14th Innovations in Theoretical Computer Science conference (ITCS)), 2021
arXiv - An Improved Random Shift Algorithm for Spanners and Low Diameter Decompositions
Sebastian Forster, Martin Grösbacher, and Tijn de Vos
Conference on Principles of Distributed Systems (OPODIS), 2021
arXiv - Dynamic Maintenance of Low-Stretch Probabilistic Tree Embeddings with Applications
Sebastian Forster, Gramoz Goranci, and Monika Henzinger
32nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2021
arXiv
Supported by the Austrian Science Fund (FWF): P 32863-N
Other Files