DID YOU KNOW? DTIC has over 3.5 million final reports on DoD funded research, development, test, and evaluation activities available to our registered users. Click
HERE to register or log in.
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
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.
Distribution Statement:
APPROVED FOR PUBLIC RELEASE