| |
Records |
Links |
|
Author |
Becker, F.; Montealegre, P.; Rapaport, I.; Todinca, I. |
|
| |
Title |
The Impact Of Locality In The Broadcast Congested Clique Model |
Type |
|
| |
Year |
2020 |
Publication |
Siam Journal On Discrete Mathematics |
Abbreviated Journal |
SIAM Discret. Math. |
|
| |
Volume |
34 |
Issue |
1 |
Pages |
682-700 |
|
| |
Keywords |
broadcast congested clique; induced cycles; graph degeneracy |
|
| |
Abstract |
The broadcast congested clique model (BCLIQUE) is a message-passing model of distributed computation where n nodes communicate with each other in synchronous rounds. First, in this paper we prove that there is a one-round, deterministic algorithm that reconstructs the input graph G if the graph is d-degenerate, and rejects otherwise, using bandwidth b = O(d . log n). Then, we introduce a new parameter to the model. We study the situation where the nodes, initially, instead of knowing their immediate neighbors, know their neighborhood up to a fixed radius r. In this new framework, denoted BCLIQuE[r], we study the problem of detecting, in G, an induced cycle of length at most k (CYCLE <= k) and the problem of detecting an induced cycle of length at least k +1 (CYCLE>k). We give upper and lower bounds. We show that if each node is allowed to see up to distance r = left perpendicular k/2 right perpendicular + 1, then a polylogarithmic bandwidth is sufficient for solving CYCLE>k with only two rounds. Nevertheless, if nodes were allowed to see up to distance r = left perpendicular k/3 right perpendicular, then any one-round algorithm that solves CYCLE>k needs the bandwidth b to be at least Omega(n/ log n). We also show the existence of a one-round, deterministic BCLIQUE algorithm that solves CYCLE <= k with bandwitdh b = O(n(1/left perpendicular k/2 right perpendicular). log n). On the negative side, we prove that, if epsilon <= 1/3 and 0 < r <= k/4, then any epsilon-error, R-round, b-bandwidth algorithm in the BCLIQUE[r] model that solves problem CYCLE(<= k )satisfies R . b = Omega(n(1/left perpendicular k/2 right perpendicular)). |
|
| |
Address |
[Becker, F.; Todinca, I] Univ Orleans, INSA Ctr Val Loire, LIFO EA 4022, Orleans, France, Email: florent.becker@univ-orleans.fr; |
|
| |
Corporate Author |
|
Thesis |
|
|
| |
Publisher |
Siam Publications |
Place of Publication |
|
Editor |
|
|
| |
Language |
English |
Summary Language |
|
Original Title |
|
|
| |
Series Editor |
|
Series Title |
|
Abbreviated Series Title |
|
|
| |
Series Volume |
|
Series Issue |
|
Edition |
|
|
| |
ISSN |
0895-4801 |
ISBN |
|
Medium |
|
|
| |
Area |
|
Expedition |
|
Conference |
|
|
| |
Notes |
WOS:000546886700033 |
Approved |
|
|
| |
Call Number |
UAI @ eduardo.moreno @ |
Serial |
1182 |
|
| Permanent link to this record |
| |
|
| |
|
Author |
Bitar, N.; Goles, E.; Montealegre, P. |
|
| |
Title |
COMPUTATIONAL COMPLEXITY OF BIASED DIFFUSION-LIMITED AGGREGATION |
Type |
|
| |
Year |
2022 |
Publication |
Siam Journal On Discrete Mathematics |
Abbreviated Journal |
SIAM Discret. Math. |
|
| |
Volume |
36 |
Issue |
1 |
Pages |
823-866 |
|
| |
Keywords |
diffusion-limited aggregation; computational complexity; space complexity; NL-completeness; P-completeness |
|
| |
Abstract |
Diffusion-Limited Aggregation (DLA) is a cluster-growth model that consists in a set of particles that are sequentially aggregated over a two-dimensional grid. In this paper, we introduce a biased version of the DLA model, in which particles are limited to move in a subset of possible directions. We denote by k-DLA the model where the particles move only in k possible directions. We study the biased DLA model from the perspective of Computational Complexity, defining two decision problems The first problem is Prediction, whose input is a site of the grid c and a sequence S of walks, representing the trajectories of a set of particles. The question is whether a particle stops at site c when sequence S is realized. The second problem is Realization, where the input is a set of positions of the grid, P. The question is whether there exists a sequence S that realizes P, i.e. all particles of S exactly occupy the positions in P. Our aim is to classify the Prediciton and Realization problems for the different versions of DLA. We first show that Prediction is P-Complete for 2-DLA (thus for 3-DLA). Later, we show that Prediction can be solved much more efficiently for 1-DLA. In fact, we show that in that case the problem is NL-Complete. With respect to Realization, we show that restricted to 2-DLA the problem is in P, while in the 1-DLA case, the problem is in L. |
|
| |
Address |
|
|
| |
Corporate Author |
|
Thesis |
|
|
| |
Publisher |
|
Place of Publication |
|
Editor |
|
|
| |
Language |
|
Summary Language |
|
Original Title |
|
|
| |
Series Editor |
|
Series Title |
|
Abbreviated Series Title |
|
|
| |
Series Volume |
|
Series Issue |
|
Edition |
|
|
| |
ISSN |
0895-4801 |
ISBN |
|
Medium |
|
|
| |
Area |
|
Expedition |
|
Conference |
|
|
| |
Notes |
WOS:000778502000037 |
Approved |
|
|
| |
Call Number |
UAI @ alexi.delcanto @ |
Serial |
1558 |
|
| Permanent link to this record |
