Research And Applications For The Problem Of Minimum Cut/Maximum Flow Algorithms

The Minimum-Cut/Maximum-Flow problem is a classic combinatorial problem that appears in many figure and abstract applications. For visible networks, the maximum traffic flow between different locations and the maximum telecommunication speed for users to users can be described as the minimum-cut/maximum-flow model, and this model for invisible networks is available too, by combining with minimizing of energy function, it separates the foreground and the background of a picture and shows the edges of the given objects in images with the cut sets. The minimumcut/maximum-flow method determines the time of image segmentation, thus research for the algorithms of this method is the key of speeding up the application.The new algorithms for the problem of minimum-cut/maximum-flow were proposed in this paper, with the study of image segmentation, some achievements as followed:1. Aimed at the low efficiency of calculating augmenting paths, advanced a restoration rule for the augmenting path algorithm based on the greedy method. The new algorithm was faster than Dinic algorithm and the highest label pre-flow push algorithm in NW small world networks and BA scalefree networks in the experiments.2. Discovered the back flow push in the pre-flow push algorithm and pointed out the stage wasted plenty of time for increasing number of hierarchical of the network. To lower the run-time, designed a back flow push detecting lowest label pre-flow push algorithm. The algorithm prevented the back flow push phenomenon and was faster in most of networks compared with the highest label pre-flow push algorithm.3. With the technology of image segmentation, the two algorithms above recognized the given objects in the pictures precisely and spent less time than the classic algorithms. Especially, the application was in real-time with the algorithm of back flow push detecting lowest label pre-flow push.4. To optimize the non-polynomial algorithm, found a multiple compression method for capacity network, with a small admissible error, the method reduced the run-time for Ford-Fulkerson algorithm and prevented from the abnormal convergency.