Maximizing residual flow under an arc destruction
Authors:
Abstract
In this paper, we consider two problems related to single‐commodity flows on a directed network. In the first problem, for a given s – t flow, if an arc is destroyed, all the flow that is passing through that arc is destroyed. What is left flowing from s to t is the residual flow. The objective is to determine a flow pattern such that the residual flow is maximized. We provide a strongly polynomial algorithm for this problem, called the maximum residual flow problem, and consider various extensions of this basic model. In the second problem, known as the “most vital arc” problem, the objective is to remove an arc so that the maximal flow on the residual network is as small as possible. Results are also derived which help implement an efficient scheme for solving this problem. © 2001 John Wiley & Sons, Inc.Keywords
This publication has 9 references indexed in Scilit:
- ε-Approximation minimization of convex functions in fixed dimensionOperations Research Letters, 1996
- Ratio combinatorial programsEuropean Journal of Operational Research, 1995
- The network inhibition problem1993
- Newton's method for fractional combinatorial optimization1992
- On the structure of all minimum cuts in a network and applications1980
- Bicriteria Transportation ProblemManagement Science, 1979
- Mathematical Techniques for Efficient Record Segmentation in Large Shared DatabasesJournal of the ACM, 1976
- Determining the most vital link in a flow networkNaval Research Logistics Quarterly, 1971
- Flows in Networks1963