Method and equipment for acquiring minimum cut of directed graphs

A directed graph, the smallest technology, applied in the field of network optimization, can solve problems such as network congestion and low performance

Active Publication Date: 2014-12-24
HUAWEI TECH CO LTD +1
View PDF3 Cites 4 Cited by
  • Summary
  • Abstract
  • Description
  • Claims
  • Application Information

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 amou

Method used

the structure of the environmentally friendly knitted fabric provided by the present invention; figure 2 Flow chart of the yarn wrapping machine for environmentally friendly knitted fabrics and storage devices; image 3 Is the parameter map of the yarn covering machine
View more

Image

Smart Image Click on the blue labels to locate them in the text.
Viewing Examples
Smart Image
  • Method and equipment for acquiring minimum cut of directed graphs
  • Method and equipment for acquiring minimum cut of directed graphs
  • Method and equipment for acquiring minimum cut of directed graphs

Examples

Experimental program
Comparison scheme
Effect test

Embodiment Construction

[0095] The following will clearly and completely describe the technical solutions in the embodiments of the present invention with reference to the accompanying drawings in the embodiments of the present invention. Obviously, the described embodiments are only some, not all, embodiments of the present invention. Based on the embodiments of the present invention, all other embodiments obtained by persons of ordinary skill in the art without making creative efforts belong to the protection scope of the present invention.

[0096] see figure 1 , is a schematic flowchart of a method for obtaining a minimum cut of a directed graph provided in this embodiment, including:

[0097] S101: According to a preset strategy, divide the directed graph into at least two sink subgraphs and at least two source subgraphs;

[0098] Exemplarily, all the sink subgraphs contain the sinks of the directed graph, and all the sink subgraphs have a sequential containment relationship; all the source poi...

the structure of the environmentally friendly knitted fabric provided by the present invention; figure 2 Flow chart of the yarn wrapping machine for environmentally friendly knitted fabrics and storage devices; image 3 Is the parameter map of the yarn covering machine
Login to view more

PUM

No PUM Login to view more

Abstract

An embodiment of the invention provides a method and equipment for acquiring minimum cut of directed graphs. The method includes respectively partitioning each directed graph into at least two meeting point sub-graphs and at least two source point sub-graphs according to preset strategies; acquiring minimum cut sets of all the meeting point sub-graphs by means of parallel computation, acquiring equivalent meeting points of the directed graphs by the aid of communication between the meeting point sub-graphs, acquiring minimum cut sets of all the source point sub-graphs by means of parallel computation and acquiring equivalent source points of the directed graphs by the aid of communication between the source point sub-graphs; acquiring the minimum cut of the directed graphs according to all connected edges of the equivalent meeting points of the directed graphs and the equivalent source points of the directed graphs. The method and the equipment for acquiring the minimum cut of the directed graphs have the advantages that the minimum cut of the directed graphs are acquired from node sets in forms of the sub-graphs in relations with one another sequentially, accordingly, communication frequencies and synchronization frequencies among active nodes during parallel computation can be reduced, and the performance can be improved.

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...

Claims

the structure of the environmentally friendly knitted fabric provided by the present invention; figure 2 Flow chart of the yarn wrapping machine for environmentally friendly knitted fabrics and storage devices; image 3 Is the parameter map of the yarn covering machine
Login to view more

Application Information

Patent Timeline
no application Login to view more
IPC IPC(8): G06F9/46
Inventor 王蕾崔慧敏冯晓兵
Owner HUAWEI TECH CO LTD
Who we serve
  • R&D Engineer
  • R&D Manager
  • IP Professional
Why Eureka
  • Industry Leading Data Capabilities
  • Powerful AI technology
  • Patent DNA Extraction
Social media
Try Eureka
PatSnap group products

Browse by: Latest US Patents, China's latest patents, Technical Efficacy Thesaurus, Application Domain, Technology Topic.

© 2024 PatSnap. All rights reserved.Legal|Privacy policy|Modern Slavery Act Transparency Statement|Sitemap