Weighted min-cut: sequential, cut-query, and streaming algorithms
Sagnik Mukhopadhyay, Danupon Nanongkai · 2020
Consider the following 2-respecting min-cut problem. Given any weighted graph G and its spanning tree T, find the minimum cut among the cuts that contain at most two edges in T. This problem is an important subroutine in Karger’s celebrated randomized near-linear-time min-cut algorithm [STOC’96]. We present a new approach for this problem which can be easily implemented in many settings, leading to the following randomized min-cut algorithms for weighted graphs.