Deterministic Subgraph Detection in Broadcast CONGEST

Janne H. Korhonen, Joel Rybicki

Tutkimustuotos: Artikkeli kirjassa/konferenssijulkaisussaConference contributionScientificvertaisarvioitu

Abstrakti

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), respectively, in the supported CONGEST model, which can be seen as an intermediate model between CONGEST and the congested clique.
AlkuperäiskieliEnglanti
Otsikko21st International Conference on Principles of Distributed Systems, OPODIS 2017
KustantajaSchloss Dagstuhl-Leibniz-Zentrum für Informatik
TilaJulkaistu - 2017
OKM-julkaisutyyppiA4 Artikkeli konferenssijulkaisuussa
TapahtumaInternational Conference on Principles of Distributed Systems - Lisbon, Portugali
Kesto: 18 jouluk. 201720 jouluk. 2017
Konferenssinumero: 21

Julkaisusarja

NimiLeibniz International Proceedings in Informatics
KustantajaSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Vuosikerta95
ISSN (elektroninen)1868-8969

Conference

ConferenceInternational Conference on Principles of Distributed Systems
LyhennettäOPODIS
Maa/AluePortugali
KaupunkiLisbon
Ajanjakso18/12/201720/12/2017

Sormenjälki

Sukella tutkimusaiheisiin 'Deterministic Subgraph Detection in Broadcast CONGEST'. Ne muodostavat yhdessä ainutlaatuisen sormenjäljen.

Siteeraa tätä