An Algorithm for Enumerating the Near-Minimum Weight S-T Cuts of a Graph
Abstract
We provide an algorithm for enumerating near-minimum weight s-t cuts in directed and undirected graphs, with applications to network interdiction and network reliability. "Near-minimum" means within a factor of l+epilson of the minimum for some epilson > 0. The algorithm is based on recursive inclusion and exclusion of edges in locally minimum-weight cuts identified with a maximum flow algorithm. We prove a polynomial-time complexity result when epilson = 0, and for epilson > 0 we demonstrate good empirical efficiency. The algorithm is programmed in Java, run on a 733 MHz Pentium III computer with 128 megabytes of memory, and tested on a number of graphs. For example, all 274,550 near-minimum cuts within 10% of the minimum weight can be obtained in 74 seconds for a 627 vertex 2,450 edge unweighted graph. All 20,806 near-minimum cuts within 20% of minimum can be enumerated in 61 seconds on the same graph with weights being uniformly distributed integers in the range 1,10.
Document Details
- Document Type
- Technical Report
- Publication Date
- Dec 01, 2000
- Accession Number
- ADA387157
Entities
People
- Ahmet Balcioglu
Organizations
- Naval Postgraduate School