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

A theorem that expresses the relation between the most positive cut problem and the minimum flow problem is proved, and a new algorithm to solve the most positive cut problem using the minimum flow algorithms is presented. The algorithm runs in the running time of the minimum flow algorithm. A theorem showing that the feasibility of a network can be distinguished by solving a minimum flow problem is proved.