[2209.11669] Improved Distributed Network Decomposition, Hitting Sets, and Spann...
source link: https://arxiv.org/abs/2209.11669
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
[Submitted on 23 Sep 2022]
Improved Distributed Network Decomposition, Hitting Sets, and Spanners, via Derandomization
This paper presents significantly improved deterministic algorithms for some of the key problems in the area of distributed graph algorithms, including network decomposition, hitting sets, and spanners. As the main ingredient in these results, we develop novel randomized distributed algorithms that we can analyze using only pairwise independence, and we can thus derandomize efficiently. As our most prominent end-result, we obtain a deterministic construction for O(\log n)-color O(\log n \cdot \log\log\log n)-strong diameter network decomposition in \tilde{O}(\log^3 n) rounds. This is the first construction that achieves almost \log n in both parameters, and it improves on a recent line of exciting progress on deterministic distributed network decompositions [Rozhoň, Ghaffari STOC'20; Ghaffari, Grunau, Rozhoň SODA'21; Chang, Ghaffari PODC'21; Elkin, Haeupler, Rozhoň, Grunau FOCS'22].
| Subjects: | Data Structures and Algorithms (cs.DS) |
| Cite as: | arXiv:2209.11669 [cs.DS] |
| (or arXiv:2209.11669v1 [cs.DS] for this version) | |
| https://doi.org/10.48550/arXiv.2209.11669 |
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK