2026-07-28T15:51:36Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:13666 2024-03-06T10:52:36Z ddc:004 open_access

Distance Computations in the Hybrid Network Model via Oracle Simulations Censor-Hillel, Keren Leitersdorf, Dean Polosukhin, Volodymyr Distributed graph algorithms Hybrid network model Distance computations The Hybrid network model was introduced in [Augustine et al., SODA '20] for laying down a theoretical foundation for networks which combine two possible modes of communication: One mode allows high-bandwidth communication with neighboring nodes, and the other allows low-bandwidth communication over few long-range connections at a time. This fundamentally abstracts networks such as hybrid data centers, and class-based software-defined networks. Our technical contribution is a density-aware approach that allows us to simulate a set of oracles for an overlay skeleton graph over a Hybrid network. As applications of our oracle simulations, with additional machinery that we provide, we derive fast algorithms for fundamental distance-related tasks. One of our core contributions is an algorithm in the Hybrid model for computing exact weighted shortest paths from Õ(n^{1/3}) sources which completes in Õ(n^{1/3}) rounds w.h.p. This improves, in both the runtime and the number of sources, upon the algorithm of [Kuhn and Schneider, PODC ’20], which computes shortest paths from a single source in Õ(n^{2/5}) rounds w.h.p. We additionally show a 2-approximation for weighted diameter and a (1+ε)-approximation for unweighted diameter, both in Õ(n^{1/3}) rounds w.h.p., which is comparable to the ̃ Ω(n^{1/3}) lower bound of [Kuhn and Schneider, PODC ’20] for a (2-ε)-approximation for weighted diameter and an exact unweighted diameter. We also provide fast distance approximations from multiple sources and fast approximations for eccentricities. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Keren Censor-Hillel and Dean Leitersdorf and Volodymyr Polosukhin 2021 Is Part Of LIPIcs, Volume 187, 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2021.21 urn:nbn:de:0030-drops-136663 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2021.21 eng https://creativecommons.org/licenses/by/4.0/legalcode