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):

• Balcioglu, Ahmet
• Wood, R. K.

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:

• *ALGORITHMS
• *GRAPHS
• NETWORKS
• INTERDICTION
• FACTOR ANALYSIS
• INTEGER PROGRAMMING
• TOPOLOGY
• POLYNOMIALS
• COMBINATORIAL ANALYSIS
• COMPUTATIONS

Subject Categories:

• Numerical Mathematics

Distribution Statement:

APPROVED FOR PUBLIC RELEASE