Fully Dynamic Min-Cut of Superconstant Size in Subpolynomial Time
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866911760192110592 |
|---|---|
| author | Jin, Wenyu Sun, Xiaorui Thorup, Mikkel |
| author_facet | Jin, Wenyu Sun, Xiaorui Thorup, Mikkel |
| contents | 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 $\widetilde O(\sqrt{n})$ for any $c > 2$ and $c = O(\log n)$ [Thorup, Combinatorica'07]. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2401_09700 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Fully Dynamic Min-Cut of Superconstant Size in Subpolynomial Time Jin, Wenyu Sun, Xiaorui Thorup, Mikkel Data Structures and Algorithms 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 $\widetilde O(\sqrt{n})$ for any $c > 2$ and $c = O(\log n)$ [Thorup, Combinatorica'07]. |
| title | Fully Dynamic Min-Cut of Superconstant Size in Subpolynomial Time |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2401.09700 |