Sublinear-time distributed algorithms for detecting small cliques and even cycles

DOI10.1007/S00446-021-00409-3MaRDI QIDQ2146871zbMATH OpenOpenAlexFDO

Authors Talya Eden, Nimrod Fiat, Orr Fischer, Fabian Kuhn, Rotem Oshman

Publication date 21 June 2022

Published in Distributed Computing (Search for Journal in Brave)

Full work available at URL https://drops.dagstuhl.de/opus/volltexte/2019/11322/

zbMATH Keywords

distributed computingCONGESTexpander decompositionsubgraph freeness

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Paths and cycles (05C38) Distributed algorithms (68W15)

Recommendations

• Sublinear-time distributed algorithms for detecting small cliques and even cycles
• Lower bounds for subgraph detection in the CONGEST model
• Detecting cliques in CONGEST networks
• Detecting cliques in CONGEST networks
• Deterministic subgraph detection in broadcast CONGEST

Cites work

• scientific article; zbMATH DE number 437558 (Why is no real title available?)
• scientific article; zbMATH DE number 1168330 (Why is no real title available?)
• scientific article; zbMATH DE number 7561283 (Why is no real title available?)
• A Bound on the Number of Edges in Graphs Without an Even Cycle
• A Note on Bipartite Graphs Without 2 k -Cycles
• Almost tight bounds for rumour spreading with conductance
• Approximating the Permanent
• Arboricity and Subgraph Listing Algorithms
• Collective dynamics of `small-world' networks
• Cycles of even length in graphs
• Derandomizing distributed algorithms with small messages: spanners and dominating set
• Detecting cliques in CONGEST networks
• Deterministic subgraph detection in broadcast CONGEST
• Distributed Graph Coloring: Fundamentals and Recent Developments
• Distributed MST and routing in almost mixing time
• Distributed Strong Diameter Network Decomposition
• Distributed discovery of large near-cliques
• Distributed edge connectivity in sublinear time
• Distributed testing of excluded subgraphs
• Distributed triangle detection via expander decomposition
• Distributed verification and hardness of distributed approximation
• Edge-Disjoint Spanning Trees of Finite Graphs
• Extremal problems for cycles in graphs
• Improved distributed expander decomposition and nearly optimal triangle enumeration
• Lower bounds for subgraph detection in the CONGEST model
• Near-optimal scheduling of distributed algorithms
• On the distributional complexity of disjointness
• On the power of the congested clique model
• Polylogarithmic-time deterministic network decomposition and distributed derandomization
• The history of degenerate (bipartite) extremal graph problems
• 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)

• On the power of threshold-based algorithms for detecting cycles in the \textsc{CONGEST} model
• On the power of threshold-based algorithms for detecting cycles in the CONGEST model
• Sublinear-time distributed algorithms for detecting small cliques and even cycles
• Deterministic subgraph detection in broadcast CONGEST
• Lower bounds for subgraph detection in the CONGEST model
• Fast distributed algorithms for girth, cycles and small subgraphs
• Detecting cliques in CONGEST networks
• Detecting cliques in CONGEST networks
• Finding cycles and trees in sublinear time
• A note on improved results for one round distributed clique listing
• Deterministic near-optimal distributed listing of cliques
• Distributed discovery of large near-cliques

This page was built for publication: Sublinear-time distributed algorithms for detecting small cliques and even cycles

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