Abstract
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].
| Original language | English |
|---|---|
| Title of host publication | Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) |
| Number of pages | 28 |
| Publisher | SIAM |
| Publication date | 2024 |
| Pages | 2999-3026 |
| DOIs | |
| Publication status | Published - 2024 |
| Event | 35th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2024 - Alexandria, United States Duration: 7 Jan 2024 → 10 Jan 2024 |
Conference
| Conference | 35th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2024 |
|---|---|
| Country/Territory | United States |
| City | Alexandria |
| Period | 07/01/2024 → 10/01/2024 |
| Sponsor | ACM Special Interest Group on Algorithms and Computation Theory (SIGACT), SIAM Activity Group on Discrete Mathematics |
Bibliographical note
Publisher Copyright:Copyright © 2024 by SIAM.