Cactus Representation of Minimum Cuts: Derandomize and Speed up
Zhongtian He, Shang-En Huang, Thatchaphol Saranurak · Society for Industrial and Applied Mathematics eBooks · 2024
Given an undirected weighted graph with n vertices and m edges, we give the first deterministic m1+o(1)-time algorithm for constructing the cactus representation of all global minimum cuts. This improves the current n2+o(1)-time state-of-the-art deterministic algorithm, which can be obtained by combining ideas implicitly from three papers [22, 27, 12]. The known explicitly stated deterministic algorithm has a runtime of Õ(mn) [9, 34]. Using our technique, we can even speed up the fastest randomized algorithm of [23] whose running time is at least Ω(m log4 n) to O(m log3 n).