2026-07-20T12:09:17Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8625 2024-03-06T10:42:10Z ddc:004 open_access

Deterministic Subgraph Detection in Broadcast CONGEST Korhonen, Janne H. Rybicki, Joel distributed computing subgraph detection CONGEST model lower bounds We present simple deterministic algorithms for subgraph finding and enumeration in the broadcast CONGEST model of distributed computation: - For any constant k, detecting k-paths and trees on k nodes can be done in O(1) rounds. - For any constant k, detecting k-cycles and pseudotrees on k nodes can be done in O(n) rounds. - On d-degenerate graphs, cliques and 4-cycles can be enumerated in O(d + log n) rounds, and 5-cycles in O(d2 + log n) rounds. In many cases, these bounds are tight up to logarithmic factors. Moreover, we show that the algorithms for d-degenerate graphs can be improved to O(d/logn) and O(d2/logn), respect- ively, in the supported CONGEST model, which can be seen as an intermediate model between CONGEST and the congested clique. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Janne H. Korhonen and Joel Rybicki 2018 Is Part Of LIPIcs, Volume 95, 21st International Conference on Principles of Distributed Systems (OPODIS 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.OPODIS.2017.4 urn:nbn:de:0030-drops-86252 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2017.4 eng https://creativecommons.org/licenses/by/3.0/legalcode