Routing schemes for hybrid communication networks

Abstract: We consider the problem of computing routing schemes in the model of distributed computing where nodes have access to two fundamentally different communication modes. In this problem nodes have to compute small labels and routing tables that allow for efficient routing of messages in the local network, which typically offers the majority of the throughput. Recent work has shown that using the model admits a significant speed-up compared to what would be possible if either communication mode were used in isolation. Nonetheless, if general graphs are used as the input graph the computation of routing schemes still takes polynomial rounds in the

model.

We bypass this lower bound by restricting the local graph to unit-disc-graphs and solve the problem deterministically with running time
, label size , and size of routing tables where is the number of “radio holes” in the network. Our work builds on recent work by Coy et al., who obtain this result in the much simpler setting where the input graph has no radio holes. We develop new techniques to achieve this, including a decomposition of the local graph into path-convex regions, where each region contains a shortest path for any pair of nodes in it

Standort
Deutsche Nationalbibliothek Frankfurt am Main
Umfang
Online-Ressource
Sprache
Englisch
Anmerkungen
Theoretical computer science. - 985 (2024) , 114352, ISSN: 1879-2294

Ereignis
Veröffentlichung
(wo)
Freiburg
(wer)
Universität
(wann)
2024
Urheber

DOI
10.1016/j.tcs.2023.114352
URN
urn:nbn:de:bsz:25-freidok-2532733
Rechteinformation
Open Access; Der Zugriff auf das Objekt ist unbeschränkt möglich.
Letzte Aktualisierung
14.08.2025, 10:46 MESZ

Datenpartner

Dieses Objekt wird bereitgestellt von:
Deutsche Nationalbibliothek. Bei Fragen zum Objekt wenden Sie sich bitte an den Datenpartner.

Beteiligte

Entstanden

  • 2024

Ähnliche Objekte (12)