Distributed Algorithms for Fundamental Graph Problems

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 – 09/2024

Associated Team Members

  • Sebastian Forster, PI
  • Elisabeth Riedl, administration
  • Aditi Dudeja, postdoc
  • Tijn de Vos, PhD student

Former Team Members

  • Judith Warter, administration
  • Emilio Cruciani, postdoc
  • Yasamin Nazari, postdoc

Publications

  • Joran van Apeldoorn and Tijn de Vos. “A Framework for Distributed Quantum Queries in the CONGEST Model”. In: Proceedings of the 2022 ACM Symposium on Distributed Computing. PODC 2022 (Salerno, Italy, July 25–29, 2022). Ed. by Alessia Milani and Philipp Woelfel. ACM, 2022, pp. 109–119. doi:  10.1145/3519270.3538413. arXiv:  2202.10969.
  • Greg Bodwin, Michael Dinitz, and Yasamin Nazari. “Vertex Fault-Tolerant Emulators”. In: 13th Innovations in Theoretical Computer Science Conference. ITCS 2022 (Berkeley, CA, USA, Jan. 31–Feb. 3, 2022). Ed. by Mark Braverman. Vol. 215. LIPIcs. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2022, 25:1–25:22. doi:  10.4230/LIPIcs.ITCS.2022.25. arXiv:  2109.08042.
  • Sebastian Forster, Gramoz Goranci, Yang P. Liu, Richard Peng, Xiaorui Sun, and Mingquan Ye. “Minor Sparsifiers and the Distributed Laplacian Paradigm”. In: 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science. FOCS 2021 (Denver, CO, USA, Feb. 7–10, 2022). IEEE, 2022, pp. 989–999. doi:  10.1109/FOCS52979.2021.00099. arXiv:  2012.15675.
  • Sebastian Forster, Martin Grösbacher, and Tijn de Vos. “An Improved Random Shift Algorithm for Spanners and Low Diameter Decompositions”. In: 25th International Conference on Principles of Distributed Systems. OPODIS 2021 (Strasbourg, France, Dec. 13–15, 2021). Ed. by Quentin Bramas, Vincent Gramoli, and Alessia Milani. Vol. 217. LIPIcs. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2022, 16:1–16:17. doi:  10.4230/LIPIcs.OPODIS.2021.16. arXiv:  2111.08975.
  • Sebastian Forster and Tijn de Vos. “Faster Cut Sparsification of Weighted Graphs”. In: 49th International Colloquium on Automata, Languages, and Programming. ICALP 2022 (Paris, France, July 4–8, 2022). Ed. by Mikolaj Bojanczyk, Emanuela Merelli, and David P. Woodruff. Vol. 229. LIPIcs. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2022, 61:1–61:19. doi:  10.4230/LIPIcs.ICALP.2022.61. arXiv:  2112.03120.
  • Sebastian Forster and Tijn de Vos. “The Laplacian Paradigm in the Broadcast Congested Clique”. In: Proceedings of the 2022 ACM Symposium on Distributed Computing. PODC 2022 (Salerno, Italy, July 25–29, 2022). Ed. by Alessia Milani and Philipp Woelfel. ACM, 2022, pp. 335–344. doi:  10.1145/3519270.3538436. arXiv:  2205.12059.
  • Jakub Lacki and Yasamin Nazari. “Near-Optimal Decremental Hopsets with Applications”. In: 49th International Colloquium on Automata, Languages, and Programming. ICALP 2022 (Paris, France, July 4–8, 2022). Ed. by Mikolaj Bojanczyk, Emanuela Merelli, and David P. Woodruff. Vol. 229. LIPIcs. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2022, 86:1–86:20. doi:  10.4230/LIPIcs.ICALP.2022.86. arXiv:  2009.08416.
  • Sebastian Forster, Gramoz Goranci, and Monika Henzinger. “Dynamic Maintenance of Low-Stretch Probabilistic Tree Embeddings with Applications”. In: Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms. SODA 2021 (Virtual Conference, Jan. 10–13, 2021). Ed. by Dániel Marx. SIAM, 2021, pp. 1226–1245. doi:  10.1137/1.9781611976465.75. arXiv:  2004.10319.

Related Activities

  • Rising Stars Talk by Yasamin Nazari at the  Fifth TCS Women Meeting at Theory Fest 2022 (Jun 20, 2022)
  • Organization of science-to-public event  “Roadshow der Jungen Akademie” by Sebastian Forster at University of Salzburg  (Jun 15, 2022)
  • Science-to-public  blog post on algorithms by Sebastian Forster in Junge-Akademie-Blog hosted by derstandard.at (Dec 12, 2021)

Related Documents

Logo of the FWF

Supported by the Austrian Science Fund (FWF): P 32863-N.