Distributed strong diameter network decomposition

DOI10.1016/j.tcs.2022.04.019OpenAlexW2277970215MaRDI QIDQ2672581

Michael Elkin, Ofer Neiman

Publication date: 13 June 2022

Published in: Theoretical Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

distributed modelnetwork decompositions

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Related Items (1)

On the Locality of Nash-Williams Forest Decomposition and Star-Forest Decomposition

Cites Work

• Nearly-linear work parallel SDD solvers, low-diameter decomposition, and low-stretch subgraphs
• Fast distributed network decompositions and covers
• Low diameter graph decompositions
• Fast distributed algorithms for (weakly) connected dominating sets and linear-size skeletons
• A log-star distributed maximal independent set algorithm for growth-bounded graphs
• On the Locality of Some NP-Complete Problems
• A Fast Network-Decomposition Algorithm and Its Applications to Constant-Time Distributed Computation
• Complexity of network synchronization
• Routing with Polynomial Communication-Space Trade-Off
• Polylogarithmic-time deterministic network decomposition and distributed derandomization
• On the locality of bounded growth
• Fast randomized algorithms for distributed edge coloring
• Distributed Strong Diameter Network Decomposition
• A randomized distributed algorithm for the maximal independent set problem in growth-bounded graphs

This page was built for publication: Distributed strong diameter network decomposition