Sagnik Mukhopadhyay
Sagnik Mukhopadhyay
Home
Experience
Publications
Contact
Project
Light
Dark
Automatic
CONGEST model
Distributed Weighted Min-Cut in Nearly-Optimal Time
Minimum-weight cut (min-cut) is a basic measure of a network’s connectivity strength. While the min-cut can be computed efficiently in the sequential setting [Karger STOC'96], there was no efficient way for a distributed network to compute its own min-cut without limiting the input structure or dropping the output quality: In the standard CONGEST model, existing algorithms with nearly-optimal time (e.
Michal Dory
,
Yuval Efron
,
Sagnik Mukhopadhyay
,
Danupon Nanongkai
Cite
×