The Impact of Locality in the Broadcast Congested Clique Model

DOI10.1137/18M1233534zbMath1432.68019MaRDI QIDQ5220411

Ivan Rapaport, Pedro Montealegre, Florent Becker, Ioan Todinca

Publication date: 20 March 2020

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

zbMATH Keywords

induced cyclesgraph degeneracybroadcast congested clique

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Distributed systems (68M14)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Cycles of even length in graphs
• The extremal function for complete minors
• Algebraic methods in the congested clique
• A faster algorithm to recognize even-hole-free graphs
• Allowing each node to communicate only once in a distributed system: shared whiteboard models
• On the power of the congested clique model
• Distributedly Testing Cycle-Freeness
• Solving the Induced Subgraph Problem in the Randomized Multiparty Simultaneous Messages Model
• A trade-off between information and communication in broadcast protocols
• NC algorithms for recognizing chordal graphs and k trees
• On the presence of disjoint subgraphs of a specified type
• Locality in Distributed Graph Algorithms
• Graph Classes: A Survey
• A new series of dense graphs of high girth
• Tree-width and circumference of graphs
• What Can be Computed Locally?
• Communication Complexity
• Proof-Labeling Schemes: Broadcast, Unicast and in Between
• Improved Massively Parallel Computation Algorithms for MIS, Matching, and Vertex Cover
• The Simultaneous Number-in-Hand Communication Model for Networks: Private Coins, Public Coins and Determinism
• Minimum-Weight Spanning Tree Construction in O(log log n) Communication Rounds

This page was built for publication: The Impact of Locality in the Broadcast Congested Clique Model