Fully Dynamic Min-Cut of Superconstant Size in Subpolynomial Time

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review

Documents

  • Fulltext

    Submitted manuscript, 394 KB, PDF document

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 languageEnglish
Title of host publicationProceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)
Number of pages28
PublisherSIAM
Publication date2024
Pages2999-3026
DOIs
Publication statusPublished - 2024
Event35th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2024 - Alexandria, United States
Duration: 7 Jan 202410 Jan 2024

Conference

Conference35th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2024
LandUnited States
ByAlexandria
Periode07/01/202410/01/2024
SponsorACM Special Interest Group on Algorithms and Computation Theory (SIGACT), SIAM Activity Group on Discrete Mathematics

Bibliographical note

Publisher Copyright:
Copyright © 2024 by SIAM.

ID: 393864354