Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | https://arxiv.org/abs/2401.10856 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866914646237118464 |
|---|---|
| author | He, Zhongtian Huang, Shang-En Saranurak, Thatchaphol |
| author_facet | He, Zhongtian Huang, Shang-En Saranurak, Thatchaphol |
| contents | 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)$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2401_10856 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Cactus Representation of Minimum Cuts: Derandomize and Speed up He, Zhongtian Huang, Shang-En Saranurak, Thatchaphol Data Structures and Algorithms 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)$. |
| title | Cactus Representation of Minimum Cuts: Derandomize and Speed up |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2401.10856 |