Distributed connectivity decomposition
Keren Censor-Hillel, Mohsen Ghaffari, Fabian Kühn · 2014
A fundamental problem in distributed network algorithms is to manage congestion and obtain information flow matching the graph's connectivity. In this paper, we present time-efficient distributed algorithms for decomposing graphs with large edge or vertex connectivity into multiple spanning or dominating trees, respectively. These decompositions allow us to achieve a flow with size close to the connectivity by parallelizing it along the trees. More specifically, our distributed decomposition algorithms are as follows: - A decomposition of each undirected graph with vertex-connectivity k into (fractionally) vertex-disjoint weighted dominating trees with total weight Ω(k/log n), in ~O(D+√n) rounds. - A decomposition of each undirected graph with edge-connectivity λ into (fractionally) edge-disjoint weighted spanning trees with total weight ⌈λ-1/2⌉(1-ε), in ~{O}(D+√nλ) rounds.