Lower Bounds for Subgraph Detection in the CONGEST Model

DOI10.4230/LIPICS.OPODIS.2017.6zbMath1487.68179OpenAlexW2794478167MaRDI QIDQ3300805

Rotem Oshman, Tzlil Gonen

Publication date: 30 July 2020

Full work available at URL: https://doi.org/10.4230/LIPIcs.OPODIS.2017.6

zbMATH Keywords

lower boundsCONGESTsubgraph freeness

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) Distributed systems (68M14)

Related Items (6)

Sublinear-time distributed algorithms for detecting small cliques and even cycles ⋮ A note on improved results for one round distributed clique listing ⋮ Detecting cliques in CONGEST networks ⋮ Unnamed Item ⋮ Unnamed Item ⋮ The Communication Complexity of Set Intersection and Multiple Equality Testing

Cites Work

• Distributed discovery of large near-cliques
• On the distributional complexity of disjointness
• Algebraic methods in the congested clique
• On the power of the congested clique model
• A sufficient condition for backtrack-bounded search
• The Probabilistic Communication Complexity of Set Intersection
• An Algorithm for Subgraph Isomorphism
• A new series of dense graphs of high girth
• Color-coding
• Communication Complexity
• “Tri, Tri Again”: Finding Triangles and Small Subgraphs in a Distributed Setting
• Triangle Finding and Listing in CONGEST Networks
• The History of Degenerate (Bipartite) Extremal Graph Problems
• Fast distributed algorithms for testing graph properties
• Three notes on distributed property testing

This page was built for publication: Lower Bounds for Subgraph Detection in the CONGEST Model