Faster Cycle Detection in the Congested Clique
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866916371787415552 |
|---|---|
| author | Censor-Hillel, Keren Even, Tomer Williams, Virginia Vassilevska |
| author_facet | Censor-Hillel, Keren Even, Tomer Williams, Virginia Vassilevska |
| contents | We provide a fast distributed algorithm for detecting $h$-cycles in the \textsf{Congested Clique} model, whose running time decreases as the number of $h$-cycles in the graph increases. In undirected graphs, constant-round algorithms are known for cycles of even length. Our algorithm greatly improves upon the state of the art for odd values of $h$. Moreover, our running time applies also to directed graphs, in which case the improvement is for all values of $h$. Further, our techniques allow us to obtain a triangle detection algorithm in the quantum variant of this model, which is faster than prior work.
A key technical contribution we develop to obtain our fast cycle detection algorithm is a new algorithm for computing the product of many pairs of small matrices in parallel, which may be of independent interest. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2408_15132 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Faster Cycle Detection in the Congested Clique Censor-Hillel, Keren Even, Tomer Williams, Virginia Vassilevska Data Structures and Algorithms Distributed, Parallel, and Cluster Computing We provide a fast distributed algorithm for detecting $h$-cycles in the \textsf{Congested Clique} model, whose running time decreases as the number of $h$-cycles in the graph increases. In undirected graphs, constant-round algorithms are known for cycles of even length. Our algorithm greatly improves upon the state of the art for odd values of $h$. Moreover, our running time applies also to directed graphs, in which case the improvement is for all values of $h$. Further, our techniques allow us to obtain a triangle detection algorithm in the quantum variant of this model, which is faster than prior work. A key technical contribution we develop to obtain our fast cycle detection algorithm is a new algorithm for computing the product of many pairs of small matrices in parallel, which may be of independent interest. |
| title | Faster Cycle Detection in the Congested Clique |
| topic | Data Structures and Algorithms Distributed, Parallel, and Cluster Computing |
| url | https://arxiv.org/abs/2408.15132 |