Detecting cliques in CONGEST networks

DOI10.1007/s00446-019-00368-wzbMath1497.68372arXiv1807.01070OpenAlexW2963207398WikidataQ126442698 ScholiaQ126442698MaRDI QIDQ2220401

Christian Konrad, Artur Czumaj

Publication date: 22 January 2021

Published in: Distributed Computing (Search for Journal in Brave)

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

zbMATH Keywords

lower boundstwo-party communicationCONGEST modelset-disjointnesssubgraph detection

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Graph theory (including graph drawing) in computer science (68R10) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Communication complexity, information complexity (68Q11)

Related Items (4)

Sublinear-time distributed algorithms for detecting small cliques and even cycles ⋮ A note on improved results for one round distributed clique listing ⋮ Distributed Testing of Graph Isomorphism in the CONGEST Model. ⋮ The Communication Complexity of Set Intersection and Multiple Equality Testing

Cites Work

• Distributed discovery of large near-cliques
• Algebraic methods in the congested clique
• On the power of the congested clique model
• Deterministic Subgraph Detection in Broadcast CONGEST.
• Lower Bounds for Subgraph Detection in the CONGEST Model
• The Probabilistic Communication Complexity of Set Intersection
• Distributed Computing: A Locality-Sensitive Approach
• Communication Complexity
• Distributed Verification and Hardness of Distributed Approximation
• “Tri, Tri Again”: Finding Triangles and Small Subgraphs in a Distributed Setting
• Improved Distributed Expander Decomposition and Nearly Optimal Triangle Enumeration
• Distributed Triangle Detection via Expander Decomposition
• Triangle Finding and Listing in CONGEST Networks
• Fast distributed algorithms for testing graph properties

This page was built for publication: Detecting cliques in CONGEST networks