Campus Event Calendar
Event Entry
What and Who
Distributed Minimum Directed Spanning Tree
Hossein Vahidi
Max-Planck-Institut für Informatik - D1
AG1 Mittagsseminar (others' work)
AG 1
AG Audience
English
Note: We use this to send email in the morning.
Date, Time and Location
Thursday, 7 May 2020
13:00
30 Minutes
000
Video only
Saarbrücken
Abstract
As part of my master's thesis, I am dealing with the problem of finding minimum directed spanning trees (MDST) in distributed models such as the k-machine model. Despite having tight results for MST in the k-machine model, the characterization of MDST is still open. To set up a baseline, I will use a conversion theorem by Klauck et al. that simulates algorithms from the Congested Clique (CC) model. The similarity between these two models is also another reason that makes it a promising starting point to study MDST in CC.
To that end, I will talk about the state-of-the-art MDST algorithm in the Congested Clique model of distributed computing, a method by Oshman and Fischer. They show that in this model, MDST can be solved in the same running time as the SSSP problem, with possibly additional polylog factors.
---------------
Join Zoom Meeting
Meeting ID: 527 278 8807
Note: for people outside D1 interested in listening to this talk, please contact Sándor Kisfaludi-Bak at skisfalu@mpi-inf.mpg.de for the password.
Contact
Sándor Kisfaludi-Bak
--email hidden
passcode not visible
logged in users only
Tags, Category, Keywords and additional notes
Join Zoom Meeting
Meeting ID: 527 278 8807
Note: for people outside D1 interested in listening to this talk, please contact Sándor Kisfaludi-Bak at skisfalu@mpi-inf.mpg.de for the password.
Meeting ID: 527 278 8807
Note: for people outside D1 interested in listening to this talk, please contact Sándor Kisfaludi-Bak at skisfalu@mpi-inf.mpg.de for the password.
Sándor Kisfaludi-Bak, 05/01/2020 09:36 -- Created document.