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

DOI10.1016/J.TCS.2024.114500OpenAlexW4392888682MaRDI QIDQ6131191FDOQ6131191

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

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

zbMATH Keywords

distributed computingcycle-freeness\textsc{CONGEST} model

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• Color-coding
• Distributed Computing: A Locality-Sensitive Approach
• On a problem of K. Zarankiewicz
• Determining the chromatic number of triangle-free \(2P_3\)-free graphs in polynomial time
• Sublinear-time distributed algorithms for detecting small cliques and even cycles
• On the power of the congested clique model
• 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)