期刊
INFORMATION SCIENCES
卷 652, 期 -, 页码 -出版社
ELSEVIER SCIENCE INC
DOI: 10.1016/j.ins.2023.119768
关键词
Minimum cut; Tree-cut mapping; Optimal pruned tree; Graph preprocessing; Acceleration
In this paper, an optimal pruned tree-based min-cut acceleration algorithm (PTMA) is proposed for the problem by exploiting the mapping between the cuts and pruned depth-first traversal trees. The algorithm can quickly obtain accurate min-cuts in dense graphs.
As an important problem in graph theory, the minimum-cut (min-cut) problem has various applications in many related fields. Among many acceleration strategies, one commonly used strategy is preprocessing the original graph to facilitate the min-cut calculations. In this paper, an optimal pruned tree-based min-cut acceleration algorithm (PTMA) is proposed for the problem by exploiting the mapping between the cuts and pruned depth-first traversal trees, which has not yet been investigated in the existing work. In different types of dense graphs with an average degree of no less than 10, using efficient dynamic programming-based preprocessing with a time complexity of O(M) (M is the total number of edges), a large number of optimal pruned depth-first traversal trees can be found, which are then used to quickly obtain accurate min-cuts of more than 99.9% node pairs. The algorithm can be used as an effective alternative to existing algorithms, and due to the inherent randomness, it is easy to fine tune the balance between overhead and precision, such as increasing the number of preprocessing passes to improve accuracy.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据