Enumerating Near-Min S-T Cuts
NAVAL POSTGRADUATE SCHOOL MONTEREY CA DEPT OF OPERATIONS RESEARCH
Pagination or Media Count:
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 1epsilon of the minimum for some epsilon greater than or equal to 0. The algorithm requires only polynomial work per cut enumerated provided that epsilon 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 epsilon and for general graph topologies.
- Numerical Mathematics