Distributed connectivity decomposition

DOI10.1145/2611462.2611491zbMath1321.68459arXiv1304.4553OpenAlexW1974912205MaRDI QIDQ2943618

Keren Censor-Hillel, Fabian Kuhn, Mohsen Ghaffari

Publication date: 3 September 2015

Published in: Proceedings of the 2014 ACM symposium on Principles of distributed computing, Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1304.4553

zbMATH Keywords

decompositiongraph connectivitydistributed algorithm

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Distributed systems (68M14) Connectivity (05C40) Distributed algorithms (68W15)

Related Items (9)

On fast and robust information spreading in the vertex-congest model ⋮ Distributed Broadcast Revisited: Towards Universal Optimality ⋮ Finding Totally Independent Spanning Trees with Linear Integer Programming ⋮ Fast Distributed Approximation for TAP and 2-Edge-Connectivity ⋮ Fast distributed approximation for TAP and 2-edge-connectivity ⋮ Distributed construction of purely additive spanners ⋮ The cost of global broadcast in dynamic radio networks ⋮ Approximation algorithms for connected maximum cut and related problems ⋮ Distributed Exact Weighted All-Pairs Shortest Paths in Randomized Near-Linear Time

This page was built for publication: Distributed connectivity decomposition