Journal
ADVANCES IN ENGINEERING SOFTWARE
Volume 173, Issue -, Pages -Publisher
ELSEVIER SCI LTD
DOI: 10.1016/j.advengsoft.2022.103256
Keywords
Minimum cut; Traversal tree; Local pruning; Graph preprocessing; Acceleration
Categories
Funding
- National Natural and Science Foundation of China [62172141, 62006071, 61772173, 61973104, 61803146]
- Natural science project of Zhengzhou science and Technology Bureau, China [21ZZXTCX20]
- Henan Excellent Young Scientists Fund [212300410036]
- Key Laboratory of Grain Information Processing and Control (Henan University of Technology)
- Ministry of Education, China [KFJJ-2016-104]
- Backbone Teacher Training Program of Henan University of Technology, China [2012012]
- Young Backbone Teacher Training Program of Henan Higher Education, China [2018GGJS066, 2019GGJS089]
- Plan For Scientific Innovation Talent of Henan University of Technology [2018RCJH07, 2018QNJH26]
- Doctor Foundation of Henan University of Technology, China [2017025]
- Natural Science Foundation of the Henan Province, China [152102210068]
- National Key Research and Development Program of China [2017YFD0401001]
- Program for Science and Technology Innovation Talents in Universities of Henan Province, China [19HASTIT027, 21HASTIT029]
- Innovative Funds Plans of Henan University of Technology, China [2020ZKCJ06]
- Cultivation Program of Young Backbone Teachers in Henan University of Technology, China [21420080]
Ask authors/readers for more resources
This article proposes a new approximation algorithm for the minimum cut (min-cut) problem in undirected graphs, which can accelerate existing methods by up to 6 orders of magnitude with limited preprocessing overhead. By checking and recording the cut values of various traversal trees, the algorithm estimates the upper bound of the min-cut value between any pair of nodes. Experimental results show that even the serial implementation of the algorithm achieves a larger acceleration ratio compared to existing methods.
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.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available