Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Thursday, June 03, 2021, 12:15 pm
Duration: 30 minutes
Location: Zoom: conference room
Speaker: Michal Dory
In a seminal work, Karger showed that the minimum cut problem reduces to a problem called the minimum 2-respecting cut problem, in which the goal is to find the minimum cut that has at most 2 edges in a certain spanning tree of the graph. I will discuss new structural observations on the minimum 2-respecting cut problem, that lead to a near optimal distributed min cut algorithm. Based on a joint work with Yuval Efron, Sagnik Mukhopadhyay and Danupon Nanongkai, to appear in STOC 2021.
Automatic MiSe System Software Version 1.4803M | admin login