Detecting cliques in CONGEST networks

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

Authors Christian Konrad, Artur Czumaj

Publication date 21 July 2022

Full work available at URL https://doi.org/10.4230/LIPICS.DISC.2018.16

zbMATH Keywords

CONGESTlower boundssubgraph detectiontwo-party communication

Mathematics Subject Classification ID

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

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

• ``Tri, tri again: finding triangles and small subgraphs in a distributed setting (extended abstract)
• 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
• scientific article; zbMATH DE number 1540669 (Why is no real title available?)
• 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

Cited in

(17)

• Sublinear-time distributed algorithms for detecting small cliques and even cycles
• Detecting cliques in CONGEST networks
• The impact of locality on the detection of cycles in the broadcast congested clique model
• Finding disjoint dense clubs in a social network
• On the power of the congested clique model
• Distributed Discovery of Large Near-Cliques
• Detecting the number of clusters in a network
• On the detection of transitive clusters in undirected networks
• Distributed detection of cliques in dynamic networks
• On designing networks resilient to clique blockers
• Sublinear-time distributed algorithms for detecting small cliques and even cycles
• Distributed distance approximation
• Connectivity lower bounds in broadcast congested clique
• Even-cycle detection in the randomized and quantum CONGEST model
• Finding clique clusters with the highest betweenness centrality
• Distributed subgraph finding: progress and challenges (invited talk)
• 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)