A Near-Optimal Low-Energy Deterministic Distributed SSSP with Ramifications on Congestion and APSP
Mohsen Ghaffari, Anton Trygub · 2024
We present a low-energy deterministic distributed algorithm that computes exact Single-Source Shortest Paths (SSSP) in near-optimal time: it runs in Õ(n) rounds and each node is awake during only poly(log n) rounds. When a node is not awake, it performs no computations or communications and spends no energy.