Query algorithm

Weighted Min-Cut: Sequential, Cut-Query and Streaming Algorithms

Consider the following 2-respecting min-cut problem. Given a 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.