The inverse maximum flow problem consideringl∞norm
Author:
- 1 July 2008
- journal article
- research article
- Published by EDP Sciences in RAIRO - Operations Research
- Vol. 42 (3) , 401-414
Abstract
The problem is to modify the capacities of the arcs from a network so that a given feasible flow becomes a maximum flow and the maximum change of the capacities on arcs is minimum. A very fast O(m⋅log(n)) time complexity algorithm for solving this problem is presented, where m is the number of arcs and n is the number of nodes of the network. The case when both, lower and upper bounds of the flow can be modified so that the given feasible flow becomes a maximum flow is also discussed. The algorithm proposed can be adapted to solve this problem, too. The inverse minimum flow problem considering l ∞ norm is also studied.Keywords
This publication has 9 references indexed in Scilit:
- The inverse maximum flow problem with lower and upper bounds for the flow2008
- Inverse minimum flow problemJournal of Applied Mathematics and Computing, 2007
- Inverse maximum flow problems under the weighted Hamming distanceJournal of Combinatorial Optimization, 2006
- Inverse Combinatorial Optimization: A Survey on Problems, Methods, and ResultsJournal of Combinatorial Optimization, 2004
- Sequential and parallel algorithms for minimum flowsJournal of Applied Mathematics and Computing, 2004
- Combinatorial algorithms for inverse network flow problemsNetworks, 2002
- An inverse Maximum capacity path problem with lower bound constraintsActa Mathematica Scientia, 2002
- Solving Inverse Spanning Tree Problems Through Network Flow TechniquesOperations Research, 1999
- Inverse maximum flow and minimum cut problemsOptimization, 1997