Mohsen Ghaffari
Rajan Udwani
ABSTRACT
In the directed single-source reachability problem, input is a directed graph G=(V, E) and a source node s, and the objective is to identify nodes t for which there is a directed path in G from s to t. Recently Nanongkai[STOC'14] presented a distributed algorithm that solves this problem in Õ(D+√nD1/2) rounds, where D and n respectively denote the network diameter and the number of nodes. This note presents an algorithm that slightly improves the round complexity to Õ(D+√nD1/4), thus getting closer to the ~Ω(D+√n) lower bound of Das Sarma et al.[STOC'11]
- A. Das Sarma, S. Holzer, L. Kor, A. Korman, D. Nanongkai, G. Pandurangan, D. Peleg, and R. Wattenhofer. Distributed verification and hardness of distributed approximation. In Proc. of the Symp. on Theory of Comp. (STOC), pages 363--372, 2011. Google Scholar
Digital Library
- D. Nanongkai. Distributed approximation algorithms for weighted shortest paths. In Proc. of the Symp. on Theory of Comp. (STOC), pages 565--573. ACM, 2014. Google ScholarDigital Library
- D. Peleg. Distributed Computing: A Locality-sensitive Approach. Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, 2000. Google ScholarCross Ref
Index Terms
- Brief Announcement: Distributed Single-Source Reachability
Recommendations
Brief Announcement: An Exponential Separation Between Randomized and Deterministic Complexity in the LOCAL Model
PODC '16: Proceedings of the 2016 ACM Symposium on Principles of Distributed ComputingOver the past 30 years numerous algorithms have been designed for symmetry breaking problems in the LOCAL model, such as maximal matching, MIS, vertex coloring, and edge-coloring. For most problems the best randomized algorithm is at least exponentially ...
Brief Announcement: Symmetry Breaking in the CONGEST Model: Time- and Message-Efficient Algorithms for Ruling Sets
PODC '17: Proceedings of the ACM Symposium on Principles of Distributed ComputingWe study local symmetry breaking problems in the Congest model, focusing on ruling set problems, which generalize the fundamental Maximal Independent Set (MIS) problem. Our work is motivated by the following central question: can we break the long-...
Brief Announcement: A Randomness-efficient Massively Parallel Algorithm for Connectivity
PODC'21: Proceedings of the 2021 ACM Symposium on Principles of Distributed ComputingWe give a randomness-efficient Massively Parallel Computation (MPC) algorithm for deciding whether an undirected graph is connected. For Connectivity on n-vertex, m-edge graphs whose components have diameter at most D = 2o(log n/ log log n), our ...
Comments