Inverse minimum flow problem

被引：10

作者：

Ciurea E. ^{[1
]}

Deaconu A. ^{[1
]}

机构：

[1] Department of Theoretical Computer Science, Transilvania University, Brasov

来源：

Journal of Applied Mathematics and Computing | 2007年 / 23卷 / 1-2期

关键词：

Graph search; Inverse problems; Maximum flow; Minimum cut; Minimum flow; Residual network;

D O I：

10.1007/BF02831968

中图分类号：

学科分类号：

摘要：

In this paper we consider the inverse minimum flow (ImF) problem, where lower and upper bounds for the flow must be changed as little as possible so that a given feasible flow becomes a minimum flow. A linear time and space method to decide if the problem has solution is presented. Strongly and weakly polynomial algorithms for solving the ImF problem are proposed. Some particular cases are studied and a numerical example is given. © 2007 Korean Society for Computational & Applied Mathematics and Korean SIGCAM.

引用

页码：193 / 203

页数：10