Node voltages in nonlinear resistive circuits enable new approach to the minimum cut problem

In our previous research, we showed that the maximum flow and the minimum cut problem can be solved by using a resistive circuit consisting of nonlinear devices with a saturation characteristic. Usually, the flow network consists of three elements, such as connectivity between nodes, branch capacities, and flows. The network information obtained from nonlinear resistive circuit analysis also has conventional three elements such as the connectivity of edge, resistances of edge (= branch capacities) and currents (= flows). In addition, each node voltage is obtained as a 4th element. In this paper, a novel minimum cut solution by using node information as 4th element is proposed in a completely different way from conventional methods. When a number of minimum cuts exist in a given flow network, there is no conventional algorithm which can simultaneously give these cuts at the moment. However, all minimum cuts can be obtained at the same time by using proposed method. Moreover, since the proposed method is realizable by a nonlinear resistive circuit, speed improvement of the minimum cut algorithm can be expected.