Fully Dynamic Min-Cut of Superconstant Size in Subpolynomial Time
Publikation: Konferencebidrag › Paper › Forskning › fagfællebedømt
We present a deterministic fully dynamic algorithm with subpolynomial worst-case time per graph update such that after processing each update of the graph, the algorithm outputs a minimum cut of the graph if the graph has a cut of size at most c for some c = (log n)o(1). Previously, the best update time was Oe(√n) for any c > 2 and c = O(log n) [28].
Originalsprog | Engelsk |
---|---|
Publikationsdato | 2024 |
Antal sider | 28 |
DOI | |
Status | Udgivet - 2024 |
Begivenhed | 35th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2024 - Alexandria, USA Varighed: 7 jan. 2024 → 10 jan. 2024 |
Konference
Konference | 35th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2024 |
---|---|
Land | USA |
By | Alexandria |
Periode | 07/01/2024 → 10/01/2024 |
Sponsor | ACM Special Interest Group on Algorithms and Computation Theory (SIGACT), SIAM Activity Group on Discrete Mathematics |
Bibliografisk note
Publisher Copyright:
Copyright © 2024 by SIAM.
ID: 390180592