Enumerating Near-Min S-T Cuts

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 1+epsilon 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.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jan 01, 2003
Accession Number
ADA495132

Entities

People

  • Ahmet Balcioglu
  • R. Kevin Wood

Organizations

  • Naval Postgraduate School

Tags

Communities of Interest

  • Advanced Electronics
  • Weapons Technologies

DTIC Thesaurus Topics

  • Algorithms
  • Applied Mathematics
  • C Programming Language
  • Computations
  • Computer Programming
  • Computer Science
  • Computers
  • Integer Programming
  • Mathematics
  • Military Applications
  • Operating Systems
  • Operations Research
  • Polynomials
  • Programming Languages
  • Reliability
  • Theoretical Computer Science
  • Topology

Readers

  • Graph Algorithms and Convex Optimization.