Gastvortrag Yasamin Nazari

“Distributed and Parallel Graph Distance Approximation”

Dienstag, 16. November 2021 um 14:00 Uhr

Hörsaal I „Christian Doppler“

(Fachbereichs Chemie und Physik der Materialien, Jakob-Haringer-Straße 2 A)

Abstract:

For many fundamental computational tasks we need to compute shortest paths in a graph efficiently. In classical settings there are many well-known efficient (and optimal) shortest path algorithms such as Dijkstra's algorithm and Bellman-Ford. However, using these classical algorithms directly is often inefficient for large-scale graph processing or when the input is distributed over a network. This has motivated studying shortest path problems on computational models that are more closely related to modern big data platforms.
In this talk we study graph distance problems on two such models, namely, the massively parallel computation (MPC) model and the Congested Clique model. We describe a graph theoretical object, called a hopset, and explain how a hopset can be utilized for computing distances more efficiently in these models.

About Yasamin Nazari:
Yasamin is a post-doctoral fellow in the Efficient Algorithms Group at University of Salzburg, working primarily with Dr. Sebastian Forster.
She received her PhD in Computer Science from Johns Hopkins University, where she was advised by Dr. Michael Dinitz. Her research focuses on graph algorithms with an emphasis on distributed and dynamic algorithms.
Prior to her PhD studies, Yasamin received a masters in computer science from University of Calgary, Canada, and completed her undergraduate studies at Shiraz University of Technology, Shiraz, Iran.

Website: http://www.cs.jhu.edu/~ynazari/