Sublinear-time distributed algorithms for detecting small cliques and even cycles
From MaRDI portal
Publication:2146871
DOI10.1007/s00446-021-00409-3zbMath1489.68397OpenAlexW3215914422MaRDI QIDQ2146871
Orr Fischer, Rotem Oshman, Nimrod Fiat, Talya Eden, Fabian Kuhn
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/
Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Distributed algorithms (68W15)
Related Items (3)
A note on improved results for one round distributed clique listing ⋮ 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
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Distributed discovery of large near-cliques
- On the distributional complexity of disjointness
- Distributed testing of excluded subgraphs
- Cycles of even length in graphs
- Algebraic methods in the congested clique
- Detecting cliques in CONGEST networks
- Near-Optimal Scheduling of Distributed Algorithms
- Almost tight bounds for rumour spreading with conductance
- On the power of the congested clique model
- Extremal problems for cycles in graphs
- Approximating the Permanent
- Edge-Disjoint Spanning Trees of Finite Graphs
- Deterministic Subgraph Detection in Broadcast CONGEST.
- Lower Bounds for Subgraph Detection in the CONGEST Model
- Arboricity and Subgraph Listing Algorithms
- Distributed Verification and Hardness of Distributed Approximation
- “Tri, Tri Again”: Finding Triangles and Small Subgraphs in a Distributed Setting
- Distributed Graph Coloring: Fundamentals and Recent Developments
- Derandomizing Distributed Algorithms with Small Messages: Spanners and Dominating Set
- Polylogarithmic-time deterministic network decomposition and distributed derandomization
- Improved Distributed Expander Decomposition and Nearly Optimal Triangle Enumeration
- Distributed edge connectivity in sublinear time
- Distributed Triangle Detection via Expander Decomposition
- Collective dynamics of ‘small-world’ networks
- Distributed Strong Diameter Network Decomposition
- A Bound on the Number of Edges in Graphs Without an Even Cycle
- Distributed MST and Routing in Almost Mixing Time
- Triangle Finding and Listing in CONGEST Networks
- The History of Degenerate (Bipartite) Extremal Graph Problems
- A Note on Bipartite Graphs Without 2 k -Cycles
- Fast distributed algorithms for testing graph properties
This page was built for publication: Sublinear-time distributed algorithms for detecting small cliques and even cycles
