A new approach for computing a most positive cut using the minimum flow algorithms

摘要

The minimum flow problem is one of the network flow problems in which computes minimum flow from a source node s to a sink node t. To this point the algorithms of the minimum flow problem have been only referred to solve certain examples like “the machine setup problem”. In this paper we describe correspondence between the minimum flow problem and the most positive cut problem. We present a new algorithm to solve the most positive cut problem using the minimum flow algorithms. The running time of the algorithm is equal to one minimum flow computation. Also we prove that the infeasibility of a network can be distinguished by solving a minimum flow problem.