arXiv:2401.10856cs.DS
Cactus Representation of Minimum Cuts: Derandomize and Speed up
Early discovery. Linked by one identifiable commenter. This paper is outside the main ranking; a mention is not an endorsement.
Abstract
Given an undirected weighted graph with $n$ vertices and $m$ edges, we give the first deterministic $m^{1+o(1)}$-time algorithm for constructing the cactus representation of \emph{all} global minimum cuts. This improves the current $n^{2+o(1)}$-time state-of-the-art deterministic algorithm, which can be obtained by combining ideas implicitly from three papers [Karger JACM'2000, Li STOC'2021, and Gabow TALG'2016] The known explicitly stated deterministic algorithm has a runtime of $\tilde{O}(mn)$ [Fleischer 1999, Nagamochi and Nakao 2000]. Using our technique, we can even speed up the fastest randomized algorithm of [Karger and Panigrahi, SODA'2009] whose running time is at least $Ω(m\log^4 n)$ to $O(m\log^3 n)$.
Fine, I edited "most" in my previous comment to "many". There are still plenty of examples (even on the first page) where the "runtime" is used to mean algorithmic complexity https://arxiv.org/abs/2401.14645 https://arxiv.org/abs/2401.13770 https://arxiv.org/abs/2401.12253…
eigenketView on HNParent context