On the power of threshold-based algorithms for detecting cycles in the \textsc{CONGEST} model

DOI10.1016/J.TCS.2024.114500MaRDI QIDQ6131191OpenAlexFDO

Authors Pierre Fraigniaud, Maël Luce, Ioan Todinca

Publication date 4 April 2024

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2024.114500

zbMATH Keywords

distributed computingcycle-freeness\textsc{CONGEST} model

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Recommendations

• On the power of threshold-based algorithms for detecting cycles in the CONGEST model
• Lower bounds for subgraph detection in the CONGEST model
• Fast distributed algorithms for girth, cycles and small subgraphs
• Sublinear-time distributed algorithms for detecting small cliques and even cycles
• Sublinear-time distributed algorithms for detecting small cliques and even cycles

Cites work

• Color-coding
• Determining the chromatic number of triangle-free \(2P_3\)-free graphs in polynomial time
• Distributed Computing: A Locality-Sensitive Approach
• On a problem of K. Zarankiewicz
• On the power of the congested clique model
• Sublinear-time distributed algorithms for detecting small cliques and even cycles
• Three notes on distributed property testing

Cited in

(1)

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

This page was built for publication: On the power of threshold-based algorithms for detecting cycles in the \textsc{CONGEST} model

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