TY - GEN

T1 - Brief announcement

AU - Montealegre, Pedro

AU - Todinca, Ioan

N1 - Publisher Copyright:
© 2016 ACM.

PY - 2016/7/25

Y1 - 2016/7/25

N2 - We present deterministic constant-round protocols for the graph connectivity problem in the model where each of the n nodes of a graph receives a row of the adjacency matrix, and broadcasts a single sublinear size message to all other nodes. Communication rounds are synchronous. This model is sometimes called the broadcast congested clique. Specifi- cally, we exhibit a deterministic protocol that computes the connected components of the input graph in [1/ϵ] rounds, each player communicating O(nϵ · log n) bits per round, with 0 < ϵ ≤ 1. We also provide a deterministic one-round protocol for connectivity, in the model when each node receives as input the graph induced by the nodes at distance at most r > 0, and communicates O(n1/r · log n) bits. This result is based on a d-pruning protocol, which consists in successively removing nodes of degree at most d until obtaining a graph with minimum degree larger than d. Our technical novelty is the introduction of deterministic sparse linear sketches: a linear compression function that permits to recover sparse Boolean vectors deterministically.

AB - We present deterministic constant-round protocols for the graph connectivity problem in the model where each of the n nodes of a graph receives a row of the adjacency matrix, and broadcasts a single sublinear size message to all other nodes. Communication rounds are synchronous. This model is sometimes called the broadcast congested clique. Specifi- cally, we exhibit a deterministic protocol that computes the connected components of the input graph in [1/ϵ] rounds, each player communicating O(nϵ · log n) bits per round, with 0 < ϵ ≤ 1. We also provide a deterministic one-round protocol for connectivity, in the model when each node receives as input the graph induced by the nodes at distance at most r > 0, and communicates O(n1/r · log n) bits. This result is based on a d-pruning protocol, which consists in successively removing nodes of degree at most d until obtaining a graph with minimum degree larger than d. Our technical novelty is the introduction of deterministic sparse linear sketches: a linear compression function that permits to recover sparse Boolean vectors deterministically.

KW - Broadcast congested clique

KW - Deterministic protocol

KW - Graph connectivity

KW - Spanning forest

UR - http://www.scopus.com/inward/record.url?scp=84984714676&partnerID=8YFLogxK

U2 - 10.1145/2933057.2933066

DO - 10.1145/2933057.2933066

M3 - Conference contribution

AN - SCOPUS:84984714676

T3 - Proceedings of the Annual ACM Symposium on Principles of Distributed Computing

SP - 245

EP - 247

BT - PODC 2016 - Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing

PB - Association for Computing Machinery

Y2 - 25 July 2016 through 28 July 2016

ER -