Enumerating Near-Min S-T Cuts
Ahmet Balcioglu, R. Kevin Wood · Kluwer Academic Publishers eBooks · 2005
We develop a factoring (partitioning) algorithm for enumerating near-minimum-weight s-t cuts in directed and undirected graphs, with application to network interdiction. “Near-minimum” means within a factor of 1+ε of the minimum for some ε ≥ 0. The algorithm requires only polynomial work per cut enumerated provided that ε is sufficiently (not trivially) small, or G has special structure, e.g., G is a complete graph. Computational results demonstrate good empirical efficiency even for large values of ε and for general graph topologies.