Potential method of nonlinear resistive circuits to solve max-flow/min-cut problems

摘要

In this paper, we propose a new potential method of nonlinear resistive circuits to solve the max-flow/min-cut problems. The important point is that simultaneous analysis of the max-flow and the min-cut can be made based on the dynamics of a single state in the circuit. Although the max-flow problem and the min-cut problem are in duality, the respective algorithms are different in conventional methods. In other words, the simultaneous analysis for the max-flow/min-cut problems does not exist. Our proposed method enables the simultaneous analysis only by nonlinear resistive circuit analysis. Additionally, the min-cut can be found from the node voltages directly. The node voltages enable the finding of all min-cuts easily when a graph has multiple min-cuts, which are found when plural cuts with the same min-cut capacity exist in the same graph. In conventional min-cut algorithms, it is hard to obtain multiple min-cuts. Moreover, our proposed method has a huge advantage of being suitable for hardware implementation. When the proposed circuit model is designed with the integrated circuit such as analog type Programmable Logic Device, Memristor or Phase Change Memory which can change graph structure and branch conductance, the novel min-cut solution with real-time processing can be expected.