Beeping Shortest Paths via Hypergraph Bipartite Decomposition
summary
Distributed beeping networks compute single and multiple shortest paths with concrete bounds: a single-path algorithm runs in O(D log log n + log^3 n) rounds and the multi‑destination algorithm runs in O(D log^2 n + log^3 n) rounds. Key technique is a new hypergraph bipartite decomposition that partitions hyperedges into Theta(log^2 n) bipartite parts, computed in O(log^3 n) rounds, which assigns small labels of size O(log log n) so each phase elects the next hop in O(log log n) rounds instead of Theta(log n).
AI-written summary · about
chapters (3)
related talks
52mFine-Grained Complexity and Algorithm Design for Graph Reachability and Distance Problems
29mParallel Cluster-BFS and Applications to Shortest Paths
35mSuperlinear Lower Bounds for Multipass Graph Processing
01h 05mGraph Algorithms in the MPC Model
46mDistributed Graph Techniques in the MPC Model
39mBroadcasting on Directed Acyclic Graphs
31mNear-Optimal Distributed Implementations of Dynamic Algorithms for Symmetry Breaking Problems
44mTutorial on List Decodable Coding Schemes and Interactive Communication in Networks (Part 2 of 2)