Pseudodeterministic Algorithms for Minimum Cut Problems
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866915698345771008 |
|---|---|
| author | Agarwala, Aryan Varma, Nithin |
| author_facet | Agarwala, Aryan Varma, Nithin |
| contents | In this paper, we present efficient pseudodeterministic algorithms for both the global minimum cut and minimum s-t cut problems. The running time of our algorithm for the global minimum cut problem is asymptotically better than the fastest sequential deterministic global minimum cut algorithm (Henzinger, Li, Rao, Wang; SODA 2024).
Furthermore, we implement our algorithm in sequential, streaming, PRAM, and cut-query models, where no efficient deterministic global minimum cut algorithms are known. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2512_23468 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Pseudodeterministic Algorithms for Minimum Cut Problems Agarwala, Aryan Varma, Nithin Data Structures and Algorithms Computational Complexity In this paper, we present efficient pseudodeterministic algorithms for both the global minimum cut and minimum s-t cut problems. The running time of our algorithm for the global minimum cut problem is asymptotically better than the fastest sequential deterministic global minimum cut algorithm (Henzinger, Li, Rao, Wang; SODA 2024). Furthermore, we implement our algorithm in sequential, streaming, PRAM, and cut-query models, where no efficient deterministic global minimum cut algorithms are known. |
| title | Pseudodeterministic Algorithms for Minimum Cut Problems |
| topic | Data Structures and Algorithms Computational Complexity |
| url | https://arxiv.org/abs/2512.23468 |