An efficient network flow code for finding all minimum cost s–t cutsets

An efficient network flow code for finding all minimum cost s–t cutsets

0.00 Avg rating0 Votes
Article ID: iaor20022479
Country: United Kingdom
Volume: 29
Issue: 3
Start Page Number: 205
End Page Number: 219
Publication Date: Mar 2002
Journal: Computers and Operations Research
Authors: , ,
Abstract:

Cutset algorithms have been well documented in the operations research literature. A directed graph is used to model the network, where each node and arc has an associated cost to cut or remove it from the graph. The problem considered in this paper is to determine all minimum cost sets of nodes and/or arcs to cut so that no directed paths exist from a specified source node s to a specified sink node t. By solving the dual maximum flow problem, it is possible to construct a binary relation associated with an optimal maximum flow such that all minimum cost s−t cutsets are identified through the set of closures for this relation. The key to our implementation is the use of graph theoretic techniques to rapidly enumerate this set of closures. Computational results are presented to suggest the efficiency of our approach.

Reviews

Required fields are marked *. Your email address will not be published.