String Problems in the Congested Clique Model
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866916685666058240 |
|---|---|
| author | Golan, Shay Kraus, Matan |
| author_facet | Golan, Shay Kraus, Matan |
| contents | In this paper we present algorithms for several string problems in the Congested Clique model. In the Congested Clique model, $n$ nodes (computers) are used to solve some problem. The input to the problem is distributed among the nodes, and the communication between the nodes is conducted in rounds. In each round, every node is allowed to send an $O(\log n)$-bit message to every other node in the network.
We consider three fundamental string problems in the Congested Clique model. First, we present an $O(1)$ rounds algorithm for string sorting that supports strings of arbitrary length. Second, we present an $O(1)$ rounds combinatorial pattern matching algorithm. Finally, we present an $O(\log\log n)$ rounds algorithm for the computation of the suffix array and the corresponding Longest Common Prefix array of a given string. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_08376 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | String Problems in the Congested Clique Model Golan, Shay Kraus, Matan Data Structures and Algorithms Distributed, Parallel, and Cluster Computing In this paper we present algorithms for several string problems in the Congested Clique model. In the Congested Clique model, $n$ nodes (computers) are used to solve some problem. The input to the problem is distributed among the nodes, and the communication between the nodes is conducted in rounds. In each round, every node is allowed to send an $O(\log n)$-bit message to every other node in the network. We consider three fundamental string problems in the Congested Clique model. First, we present an $O(1)$ rounds algorithm for string sorting that supports strings of arbitrary length. Second, we present an $O(1)$ rounds combinatorial pattern matching algorithm. Finally, we present an $O(\log\log n)$ rounds algorithm for the computation of the suffix array and the corresponding Longest Common Prefix array of a given string. |
| title | String Problems in the Congested Clique Model |
| topic | Data Structures and Algorithms Distributed, Parallel, and Cluster Computing |
| url | https://arxiv.org/abs/2504.08376 |