Computing a feasible flow or diagnosing infeasibility of a network flow in O(mn log U) time

The feasibility problem can be solved by one maximum flow computation[1, Page 169]. A new method to the problem was given in [2], which runs in O(m2 log(nU)) time,where n, m and U are the number of nodes, arcs, and the value of maximum upper bound, respectively. The merit of the method in[2], in comparison with the maximum flow algorithms, is that it presents some useful information to modeler to estimate the maximum cost of adjusting the infeasible network[10, Page 435]. Recently, [3] presented an improved implementation of the method in [2], which runs in O(mn lognU) time.The method of [2,3] only diagnoses feasibility or infeasibility of a given network, but it dose not compute a feasible flow whenit is feasible. In this paper, a modified version of the algorithm in[3] is presented. This version not only improves the running time of the algorithm to O(mn logU) time, but also it computes a feasible flow when it is feasible

کلیدواژه ها:

operations research ، optimization ، network flows ، feasibility problem