High-precision ultra-fast minimum cut approximation through aggregated hash of cut collection

Weibing Liu, Peng Li and Weibin Yao

Chaos, Solitons & Fractals, 2024, vol. 187, issue C

Abstract: Due to the wide application of s-t minimum cut (min-cut) in various scenarios, many acceleration algorithms have been proposed to solve it. However, the query times of the acceleration algorithms currently available are still high in large-scale graphs, rendering them useless in frequently solving scenarios. We re-examine the min-cut problem from a novel perspective of cut collection hash. By extracting aggregated hashes of mapped cut collections in one-dimensional space, a Monte Carlo-like method is used to quickly compare them and estimate the minimum cut between any two nodes with low computational effort and high accuracy. After the graph is preprocessed using a few hundred depth-first traversals, the time complexity of the min-cut solution can be logarithmic in terms of the average degree and capacity of the graph. Experiments on large-scale graphs show that compared to the fastest exact algorithm, the proposed algorithm can increase the speed of the min-cut solution by up to seven orders of magnitude, when only a few mathematical comparisons per pair are needed to obtain exact min-cut values of no less than 99.9% node pairs.

Keywords: Minimum cut; Cut collection; Hash; Monte Carlo algorithm; One-dimensional space; Acceleration (search for similar items in EconPapers)
Date: 2024
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0960077924009573
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:chsofr:v:187:y:2024:i:c:s0960077924009573

DOI: 10.1016/j.chaos.2024.115405

Access Statistics for this article

Chaos, Solitons & Fractals is currently edited by Stefano Boccaletti and Stelios Bekiros

More articles in Chaos, Solitons & Fractals from Elsevier
Bibliographic data for series maintained by Thayer, Thomas R. ().