Weighted min-cut: sequential, cut-query, and streaming algorithms
Sagnik Mukhopadhyay, Danupon Nanongkai
Abstract
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.
Topics & Concepts
CombinatoricsBinary logarithmLog-log plotMinimum cutMathematicsUpper and lower boundsSubroutineGraphSimple (philosophy)Streaming algorithmAlgorithmDiscrete mathematicsComputer sciencePhilosophyMathematical analysisEpistemologyOperating systemComplexity and Algorithms in GraphsPrivacy-Preserving Technologies in DataCryptography and Data Security