On the power of threshold-based algorithms for detecting cycles in the CONGEST model

DOI10.1007/978-3-031-32733-9_20arXiv2304.02360OpenAlexW4377971985MaRDI QIDQ6148078

Ioan Todinca, Pierre Fraigniaud, Maël Luce

Publication date: 11 January 2024

Published in: Structural Information and Communication Complexity (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2304.02360

zbMATH Keywords

distributed computingcycle-freeness\textsc{congest} model

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computer system organization (68Mxx) Communication complexity, information complexity (68Q11)

Cites Work

• Determining the chromatic number of triangle-free \(2P_3\)-free graphs in polynomial time
• Algebraic methods in the congested clique
• Sublinear-time distributed algorithms for detecting small cliques and even cycles
• On the power of the congested clique model
• Deterministic Subgraph Detection in Broadcast CONGEST.
• Color-coding
• Distributed Computing: A Locality-Sensitive Approach
• On a problem of K. Zarankiewicz