Title:
METHOD AND APPARATUS FOR REDUCING NETWORK FLOW GRAPH
Document Type and Number:
WIPO Patent Application WO/2015/043385
Kind Code:
A1
Abstract:
Embodiments of the present invention provide a method and an apparatus for reducing a network flow graph. The method comprises: obtaining first network flow subgraphs from a to-be-processed network flow graph, the first network flow subgraphs comprising M nodes and edges between the M nodes, and the M nodes comprising a first endpoint; combining the first network flow subgraphs into a first node; and forming a first reduction network flow graph by the first node and second network flow subgraphs except the first network flow subgraphs in the to-be-processed network flow graph, a capacity (a maximum flow value) of a minimum cut of the first reduction network flow graph being equal to a capacity (a maximum flow value) of a minimum cut of the to-be-processed network flow graph, and the first node being a first endpoint of the first reduction network flow graph, so that a scale of a graph can be effectively reduced. According to the embodiments of the present invention, a to-be-processed network flow graph does not need to conform to a certain rule, so that a process of reducing a scale of a graph has universal applicability.
Inventors:
WANG LEI (CN)
CUI HUIMIN (CN)
FENG XIAOBING (CN)
CUI HUIMIN (CN)
FENG XIAOBING (CN)
Application Number:
PCT/CN2014/086482
Publication Date:
April 02, 2015
Filing Date:
September 15, 2014
Export Citation:
Assignee:
HUAWEI TECH CO LTD (CN)
International Classes:
G06F17/10
Foreign References:
| US20080222614A1 | 2008-09-11 | |||
| CN101833553A | 2010-09-15 | |||
| CN103189836A | 2013-07-03 | |||
| US20130132442A1 | 2013-05-23 | |||
| US20130024479A1 | 2013-01-24 |
Download PDF: