Weighted Minimum Cuts and Near-Minimum Cut EstimationResearch Paper
A minimum cut of a graph with positive edge capacities is a cheapest way to disconnect it. Minimum cuts measure network reliability, and they are a basic subroutine in clustering, network design and the estimation of disconnection probabilities. A graph can have many minimum cuts: a cycle on vertices has of them. The cactus representation of…