论文部分内容阅读
针对容量型最小费用流逆问题的可行性及相关优化进行研究,证明了判断容量型最小费用流逆问题是否可行可以在多项式时间内完成.如果容量型最小费用流逆问题不可行,即无论怎样修改容量的上界u和下界l,初始流f^0都不能变为新网络的最小费用流.给出了两种调整初始流f^0的算法,证明了通过最少修改初始流f^0,可以使最小费用流逆问题变为可行.