In the distributed setting, the only existing constructions of \textit{ sparse skeletons}, (i.e., subgraphs with $O(n)$ edges) either use randomization or large messages, or require $\Omega(D)$ time, where $D$ is the hop-diameter of the input graph $G$. We devise the first deterministic distributed algorithm in the CONGEST model (i.e., uses small messages) for constructing linear-size skeletons in time $2^{ O(\sqrt{ { \log n}\cdot{ \log{ \log n}}})}$. We can also compute a linear-size spanner with stretch $polylog(n)$ in low deterministic polynomial time, i.e., $O(n^\rho)$ for an arbitrarily small constant $\rho >0$, in the CONGEST model. Yet another algorithm that we devise runs in $O({ \log n})^{ \kappa-1}$ time, for a parameter $\kappa=1,2,\dots,$ and constructs an $O({ \log n})^{ \kappa-1}$ spanner with $O(n^{ 1+1/\kappa})$ edges. All our distributed algorithms are lightweight from the computational perspective, i.e., none of them employs any heavy computations.
Categories: cs.DC cs.DS