Fully Dynamic Min-Cut of Superconstant Size in Subpolynomial Time

Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

Standard

Fully Dynamic Min-Cut of Superconstant Size in Subpolynomial Time. / Jin, Wenyu; Sun, Xiaorui; Thorup, Mikkel.

Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). SIAM, 2024. p. 2999-3026.

Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

Harvard

Jin, W, Sun, X & Thorup, M 2024, Fully Dynamic Min-Cut of Superconstant Size in Subpolynomial Time. in Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). SIAM, pp. 2999-3026, 35th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2024, Alexandria, United States, 07/01/2024. https://doi.org/10.1137/1.9781611977912.107

APA

Jin, W., Sun, X., & Thorup, M. (2024). Fully Dynamic Min-Cut of Superconstant Size in Subpolynomial Time. In Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) (pp. 2999-3026). SIAM. https://doi.org/10.1137/1.9781611977912.107

Vancouver

Jin W, Sun X, Thorup M. Fully Dynamic Min-Cut of Superconstant Size in Subpolynomial Time. In Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). SIAM. 2024. p. 2999-3026 https://doi.org/10.1137/1.9781611977912.107

Author

Jin, Wenyu ; Sun, Xiaorui ; Thorup, Mikkel. / Fully Dynamic Min-Cut of Superconstant Size in Subpolynomial Time. Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). SIAM, 2024. pp. 2999-3026

Bibtex

@inproceedings{286bc8cb6a8f4839a333ed1ef6248ed2,
title = "Fully Dynamic Min-Cut of Superconstant Size in Subpolynomial Time",
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].",
author = "Wenyu Jin and Xiaorui Sun and Mikkel Thorup",
note = "Publisher Copyright: Copyright {\textcopyright} 2024 by SIAM.; 35th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2024 ; Conference date: 07-01-2024 Through 10-01-2024",
year = "2024",
doi = "10.1137/1.9781611977912.107",
language = "English",
pages = "2999--3026",
booktitle = "Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)",
publisher = "SIAM",

}

RIS

TY - GEN

T1 - Fully Dynamic Min-Cut of Superconstant Size in Subpolynomial Time

AU - Jin, Wenyu

AU - Sun, Xiaorui

AU - Thorup, Mikkel

N1 - Publisher Copyright: Copyright © 2024 by SIAM.

PY - 2024

Y1 - 2024

N2 - 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].

AB - 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].

U2 - 10.1137/1.9781611977912.107

DO - 10.1137/1.9781611977912.107

M3 - Article in proceedings

AN - SCOPUS:85188314709

SP - 2999

EP - 3026

BT - Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)

PB - SIAM

T2 - 35th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2024

Y2 - 7 January 2024 through 10 January 2024

ER -

ID: 393864354