Detecting cliques in CONGEST networks

DOI10.4230/LIPICS.DISC.2018.16zbMATH Open1497.68373MaRDI QIDQ5090906FDOQ5090906

Authors: Christian Konrad, Artur Czumaj 

Publication date: 21 July 2022

Recommendations

• Detecting cliques in CONGEST networks
• On the power of the congested clique model
• Sublinear-time distributed algorithms for detecting small cliques and even cycles
• Sublinear-time distributed algorithms for detecting small cliques and even cycles
• Triangle Finding and Listing in CONGEST Networks

zbMATH Keywords

lower boundsCONGESTtwo-party communicationsubgraph detection

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Distributed algorithms (68W15) Communication complexity, information complexity (68Q11)

Cites Work

• Title not available (Why is that?)
• Distributed Computing: A Locality-Sensitive Approach
• The Probabilistic Communication Complexity of Set Intersection
• Communication Complexity
• Distributed discovery of large near-cliques
• On the power of the congested clique model
• ``Tri, tri again: finding triangles and small subgraphs in a distributed setting (extended abstract)
• Three notes on distributed property testing
• Distributed triangle detection via expander decomposition
• Triangle Finding and Listing in CONGEST Networks
• Deterministic subgraph detection in broadcast CONGEST
• Lower bounds for subgraph detection in the CONGEST model
• Quadratic and near-quadratic lower bounds for the CONGEST model

Cited In (12)

• Distributed detection of cliques in dynamic networks
• Sublinear-time distributed algorithms for detecting small cliques and even cycles
• Sublinear-time distributed algorithms for detecting small cliques and even cycles
• On the detection of transitive clusters in undirected networks
• Finding clique clusters with the highest betweenness centrality
• Finding disjoint dense clubs in a social network
• Detecting cliques in CONGEST networks
• Distributed Discovery of Large Near-Cliques
• Detecting the number of clusters in a network
• The impact of locality on the detection of cycles in the broadcast congested clique model
• On designing networks resilient to clique blockers
• Very large cliques are easy to detect

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5090906)