An algorithm for enumerating the near-minimum weight s-t cuts of a graph Ahmet Balcioglu

Loading...
Thumbnail Image
Authors
Balcioglu, Ahmet
Subjects
Advisors
Wood, R. Kevin
Rasmussen, Craig W.
Date of Issue
2000-12
Date
2000
Publisher
Monterey, California. Naval Postgraduate School
Language
en_US
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.
Type
Thesis
Description
Series/Report No
Department
Organization
Identifiers
NPS Report Number
Sponsors
Funder
Format
xvi, 45 p.;28 cm.
Citation
Distribution Statement
Approved for public release; distribution is unlimited.
Rights
Collections