2026-08-16T07:05:13Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:9662 2024-03-06T10:44:39Z ddc:004 open_access

Tight Bounds for Deterministic h-Shot Broadcast in Ad-Hoc Directed Radio Networks Pagourtzis, Aris Radzik, Tomasz Ad-hoc radio networks wireless networks deterministic broadcast adaptive protocols limited transmissions We consider the classical broadcast problem in ad-hoc (that is, unknown topology) directed radio networks with no collision detection, under the additional assumption that at most h transmissions (shots) are available per node. We focus on adaptive deterministic protocols for small values of h. We provide asymptotically matching lower and upper bounds for the cases h=2 and h=3. While for h=2 our bound is quadratic, similar to the bound obtained for oblivious protocols, for h=3 we prove a sub-quadratic bound of Theta(n^2 log log n / log n), where n is the number of nodes in the network. The latter is the first result showing an adaptive algorithm which is asymptotically faster than oblivious h-shot broadcast protocols, for which a tight quadratic bound is known for every constant h. Our upper bound for h=3 is constructive, making use of constructions of graphs with large girth. We also show an improved upper bound of O(n^(1+alpha/sqrt{h})) for h >= 4, where alpha is an absolute constant independent of h. Our upper bound for h >= 4 is non-constructive. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Aris Pagourtzis and Tomasz Radzik 2018 Is Part Of LIPIcs, Volume 117, 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2018.80 urn:nbn:de:0030-drops-96629 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2018.80 eng https://creativecommons.org/licenses/by/3.0/legalcode