Distributed connectivity decomposition

DOI10.1145/2611462.2611491zbMath1321.68459arXiv1304.4553MaRDI 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

decomposition; graph connectivity; distributed algorithm

Mathematics Subject Classification ID

68R10: Graph theory (including graph drawing) in computer science

05C70: Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)

05C85: Graph algorithms (graph-theoretic aspects)

05C69: Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)

68M14: Distributed systems

05C40: Connectivity

68W15: Distributed algorithms

Related Items

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