Fast Computation of Small Cuts via Cycle Space Sampling

David Pritchard, Ramakrishna Thurimella

We describe a new sampling-based method to determine cuts in an undirected graph. For a graph (V, E), its cycle space is the family of all subsets of E that have even degree at eac…