|   | 
Details
   web
Record
Author Becker, F.; Montealecre, P.; Rapaport, I.; Todinca, I.
Title The Impact Of Locality In The Broadcast Congested Clique Model Type Journal Article
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 no
Call Number UAI @ eduardo.moreno @ Serial 1182
Permanent link to this record