Deterministic subgraph detection in broadcast CONGEST

Show full item record



Permalink

http://hdl.handle.net/10138/299847

Citation

Korhonen , J H & Rybicki , J 2018 , Deterministic subgraph detection in broadcast CONGEST . in J Aspnes , A Bessani , P Felber & J Leitão (eds) , 21st International Conference on Principles of Distributed Systems (OPODIS 2017) . , 4 , Leibniz International Proceedings in Informatics (LIPIcs) , vol. 95 , Schloss Dagstuhl - Leibniz-Zentrum für Informatik , Wadern , International Conference on Principles of Distributed Systems , Lisbon , Portugal , 18/12/2017 . https://doi.org/10.4230/LIPIcs.OPODIS.2017.4

Title: Deterministic subgraph detection in broadcast CONGEST
Author: Korhonen, J.H.; Rybicki, J.
Editor: Aspnes, James; Bessani, Alysson; Felber, Pascal; Leitão, João
Contributor: University of Helsinki, Aalto University
University of Helsinki, Centre of Excellence in Metapopulation Research
Publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
Date: 2018
Language: eng
Number of pages: 16
Belongs to series: 21st International Conference on Principles of Distributed Systems (OPODIS 2017)
Belongs to series: Leibniz International Proceedings in Informatics (LIPIcs)
URI: http://hdl.handle.net/10138/299847
Abstract: 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/ log n) and O(d2/log n), respectively, in the supported CONGEST model, which can be seen as an intermediate model between CONGEST and the congested clique. © 2017 Janne H. Korhonen and Joel Rybicki.
Subject: Degenerate graphs
Deterministic algorithms
Distributed computations
Intermediate model
K -cycle
K-paths
Lower bounds
Subgraphs, Distributed computer systems
113 Computer and information sciences
Rights:


Files in this item

Total number of downloads: Loading...

Files Size Format View
LIPIcs_OPODIS_2017_4_4.pdf 645.9Kb PDF View/Open

This item appears in the following Collection(s)

Show full item record