Detecting cliques in CONGEST networks

DOI10.4230/LIPICS.DISC.2018.16MaRDI QIDQ5090906zbMATH OpenFDO

Authors Christian Konrad, Artur Czumaj

Publication date 21 July 2022

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)

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

Cites work

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

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
• Finding clique clusters with the highest betweenness centrality
• On the detection of transitive clusters in undirected networks
• 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)