2026-07-23T08:19:31Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:17548 2024-03-06T10:59:53Z ddc:004 open_access

Beeping Shortest Paths via Hypergraph Bipartite Decomposition Dufoulon, Fabien Emek, Yuval Gelles, Ran Beeping Networks Shortest Paths Hypergraph Bipartite Decomposition Constructing a shortest path between two network nodes is a fundamental task in distributed computing. This work develops schemes for the construction of shortest paths in randomized beeping networks between a predetermined source node and an arbitrary set of destination nodes. Our first scheme constructs a (single) shortest path to an arbitrary destination in O(D log log n + log³ n) rounds with high probability. Our second scheme constructs multiple shortest paths, one per each destination, in O(D log² n + log³ n) rounds with high probability. Our schemes are based on a reduction of the above shortest path construction tasks to a decomposition of hypergraphs into bipartite hypergraphs: We develop a beeping procedure that partitions the hyperedge set of a hypergraph H = (V_H, E_H) into k = Θ (log² n) disjoint subsets F₁ ∪ ⋯ ∪ F_k = E_H such that the (sub-)hypergraph (V_H, F_i) is bipartite in the sense that there exists a vertex subset U ⊆ V such that |U ∩ e| = 1 for every e ∈ F_i. This procedure turns out to be instrumental in speeding up shortest path constructions under the beeping model. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Fabien Dufoulon and Yuval Emek and Ran Gelles 2023 Is Part Of LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITCS.2023.45 urn:nbn:de:0030-drops-175485 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.45 eng https://creativecommons.org/licenses/by/4.0/legalcode