Inverse maximum flow and minimum cut problems

1 January 1997

journal article
research article
Published by Taylor & Francis in Optimization

Vol. 40 (2) , 147-170
https://doi.org/10.1080/02331939708844306

Abstract

In this paper we consider two inverse problems in combinatorial optimization: inverse maximum flow (IMF) problem and inverse minimum cut (IMC) problem. IMF (or IMC) problem can be described as: how to change the capacity vector C of a network as little as possible so that a given flow (or cut) becomes a maximum flow (or minimum cut) in the network. After discussing some characteristics of these problems, we propose strongly polynormial algorithms for the two inverse problems.

Keywords

This publication has 4 references indexed in Scilit:

A network flow method for solving some inverse combinatorial optimization problems
Optimization, 1996
A column generation method for inverse shortest path problems
Mathematical Methods of Operations Research, 1995
An inverse problem of the weighted shortest path problem
Japan Journal of Industrial and Applied Mathematics, 1995
On an instance of the inverse shortest paths problem
Mathematical Programming, 1992