Accession Number:
ADA495132
Title:
Enumerating Near-Min S-T Cuts
Descriptive Note:
Book chapter
Corporate Author:
NAVAL POSTGRADUATE SCHOOL MONTEREY CA DEPT OF OPERATIONS RESEARCH
Personal Author(s):
Report Date:
2003-01-01
Pagination or Media Count:
30.0
Abstract:
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.
Descriptors:
Subject Categories:
- Numerical Mathematics