Graph reconstruction in the congested clique

DOI10.1016/j.jcss.2020.04.004zbMath1444.68151arXiv1706.03107OpenAlexW3021194740MaRDI QIDQ2186818

Ioan Todinca, Ivan Rapaport, Pedro Montealegre, Sebastian Perez-Salazar

Publication date: 9 June 2020

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1706.03107

zbMATH Keywords

distributed computingreconstruction problemgraph classesround complexitycongested clique

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Distributed algorithms (68W15)

Related Items (2)

Deterministic size discovery and topology recognition in radio networks with short labels ⋮ Brief Announcement: What Can We Compute in a Single Round of the Congested Clique?

Uses Software

• MapReduce
• Hadoop
• Dryad
• Pregel
• Spark

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A survey of the algorithmic aspects of modular decomposition
• Distance-hereditary graphs
• On the size of hereditary classes of graphs
• A single-exponential fixed-parameter algorithm for distance-hereditary vertex deletion
• Algorithms parameterized by vertex cover and modular width, through potential maximal cliques
• Algebraic methods in the congested clique
• Toward Optimal Bounds in the Congested Clique
• Parameterized Algorithms for Modular-Width
• On the power of the congested clique model
• Polynomial Codes Over Certain Finite Fields
• Solving the Induced Subgraph Problem in the Randomized Multiparty Simultaneous Messages Model
• Fast Probabilistic Algorithms for Verification of Polynomial Identities
• Graph Classes: A Survey
• An Improved Distributed Algorithm for Maximal Independent Set
• Communication Steps for Parallel Query Processing
• Optimal deterministic routing and sorting on the congested clique
• MST in Log-Star Rounds of Congested Clique
• Brief Announcement
• Distributed Computation of Large-scale Graph Problems
• Distributed MIS via All-to-All Communication
• Lessons from the Congested Clique Applied to MapReduce
• Minimum-Weight Spanning Tree Construction in O(log log n) Communication Rounds

This page was built for publication: Graph reconstruction in the congested clique