Accelerate minimum cut calculation by tree-cut mapping with local pruning

doi:10.1016/j.advengsoft.2022.103256

Accelerate minimum cut calculation by tree-cut mapping with local pruning

2022-11-01

0

PRE

AI

DOI：10.1016/j.advengsoft.2022.103256

原文链接

原文求助

摘要

En 中文

As a fundamental problem in graph theory, the minimum cut (min-cut) problem and solutions have many applications in networking related researches. A new approximation algorithm for the problem in undirected graph is proposed that can accelerate existing method by up to 6 orders of magnitude, while the preprocessing overhead is just a limited number of depth-first traversing. In the algorithm, after checking and recording the cut values of various types of traversal trees, the good upper bound on the min-cut value between any node pair can be approximated using the minimal cut value of all related traversal trees, and the upper bound is very likely to be the exact value. The independence between different traversal passes makes it ready for further acceleration using parallelization. The traversal tree-cut mapping algorithm with local pruning (TCLP) is compared with other methods using random, scale-free and real-world graphs, the results show that even the serial implementation of TCLP can achieve far larger acceleration ratio than existing methods while obtaining exact min-cut value of 99.9% node pairs. The results also indicate that TCLP is general enough to not rely on any special local graph structure and is seldom affected by graph types, thus can be used as an effective supplement to the existing methods.

Keyword:

Minimum cut

Traversal tree

Local pruning

Graph preprocessing

Acceleration

Accelerate minimum cut calculation by tree-cut mapping with local pruning

摘要

期刊

机构

引用论文