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

Sagnik Mukhopadhyay, Danupon Nanongkai

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$…