A method and device for obtaining a minimum cut of a directed graph

Abstract

The embodiment of the present invention provides a method and device for obtaining the minimum cut of a directed graph. The method and device for obtaining the minimum cut of a directed graph on a node set in the form of a subgraph with a sequential containment relationship reduce the time required for parallel computing. The number of communications and synchronization times between the active nodes of the active node improves the performance, wherein the method includes: dividing the directed graph into at least two subgraphs of sink points and at least two subgraphs of source points respectively according to a preset strategy; parallel computing all The minimum cut set of the sink subgraph and the equivalent sink of the directed graph are obtained through the communication between the sink subgraphs, and the minimum cut set of all the source point subgraphs is calculated in parallel and the directed graph is obtained through the communication between the source point subgraphs The equivalent source point of the directed graph; obtain the minimum cut of the directed graph according to all the edges connected by the equivalent sink point of the directed graph and the equivalent source point of the directed graph.

Description

technical field [0001] The invention relates to the field of network optimization, in particular to a method and equipment for obtaining the minimum cut of a directed graph. Background technique [0002] The maximum flow minimum cut problem is a classic problem in the field of network optimization, which can be widely used in the application background with the network as the form of expression. The methods proposed for this problem are all based on the parallel computing of the nodes in the network. Active nodes are processed in parallel through the overall synchronous parallel computing model (Bulk Synchronous Parallel Computing Model, BSP model), and each active node is calculated through superstep until there are no active nodes in the entire network, and the calculation ends. [0003] The inventors found that the above methods have the following problems: during the calculation process of each superstep, a large amount of communication and synchronization between active...

AI Technical Summary

Problems solved by technology

[0003] The inventor found that the above method has the following problems: During the calculation process of each superstep, a large amount of communication and synchronization between active nodes are required, which leads to network congestion and extremely low performance

Images