License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.OPODIS.2020.31
URN: urn:nbn:de:0030-drops-135165
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/13516/
Feldmann, Michael ;
Hinnenthal, Kristian ;
Scheideler, Christian
Fast Hybrid Network Algorithms for Shortest Paths in Sparse Graphs
Abstract
We consider the problem of computing shortest paths in hybrid networks, in which nodes can make use of different communication modes. For example, mobile phones may use ad-hoc connections via Bluetooth or Wi-Fi in addition to the cellular network to solve tasks more efficiently. Like in this case, the different communication modes may differ considerably in range, bandwidth, and flexibility. We build upon the model of Augustine et al. [SODA '20], which captures these differences by a local and a global mode. Specifically, the local edges model a fixed communication network in which O(1) messages of size O(log n) can be sent over every edge in each synchronous round. The global edges form a clique, but nodes are only allowed to send and receive a total of at most O(log n) messages over global edges, which restricts the nodes to use these edges only very sparsely.
We demonstrate the power of hybrid networks by presenting algorithms to compute Single-Source Shortest Paths and the diameter very efficiently in sparse graphs. Specifically, we present exact O(log n) time algorithms for cactus graphs (i.e., graphs in which each edge is contained in at most one cycle), and 3-approximations for graphs that have at most n + O(n^{1/3}) edges and arboricity O(log n). For these graph classes, our algorithms provide exponentially faster solutions than the best known algorithms for general graphs in this model. Beyond shortest paths, we also provide a variety of useful tools and techniques for hybrid networks, which may be of independent interest.
BibTeX - Entry
@InProceedings{feldmann_et_al:LIPIcs:2021:13516,
author = {Michael Feldmann and Kristian Hinnenthal and Christian Scheideler},
title = {{Fast Hybrid Network Algorithms for Shortest Paths in Sparse Graphs}},
booktitle = {24th International Conference on Principles of Distributed Systems (OPODIS 2020)},
pages = {31:1--31:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-176-4},
ISSN = {1868-8969},
year = {2021},
volume = {184},
editor = {Quentin Bramas and Rotem Oshman and Paolo Romano},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/13516},
URN = {urn:nbn:de:0030-drops-135165},
doi = {10.4230/LIPIcs.OPODIS.2020.31},
annote = {Keywords: hybrid networks, overlay networks, sparse graphs, cactus graphs}
}
|
Keywords: |
|
hybrid networks, overlay networks, sparse graphs, cactus graphs |
|
Collection: |
|
24th International Conference on Principles of Distributed Systems (OPODIS 2020) |
|
Issue Date: |
|
2021 |
|
Date of publication: |
|
25.01.2021 |
