Fast distributed network decompositions and covers

DOI10.1006/JPDC.1996.0159MaRDI QIDQ676658zbMATH OpenOpenAlexFDO

Authors Baruch Awerbuch, Bonnie Berger, David Peleg, Lenore J. Cowen

Publication date 1996

Published in Journal of Parallel and Distributed Computing (Search for Journal in Brave)

Copyright license Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International

Full work available at URL https://semanticscholar.org/paper/8c82e010ffef16086005e87ec39ac443bdd170a3

zbMATH Keywords

deterministic sublinear-time distributed algorithmsnetwork decomposition

Mathematics Subject Classification ID

Network design and communication in computer systems (68M10) Parallel algorithms in computer science (68W10)

Recommendations

• Fast network decomposition
• Improved network decompositions using small messages with applications on MIS, neighborhood covers, and beyond
• A fast network-decomposition algorithm and its applications to constant-time distributed computation (extended abstract)
• A fast network-decomposition algorithm and its applications to constant-time distributed computation
• Near-Linear Time Construction of Sparse Neighborhood Covers

Cited in

(18)

• Simple and efficient network decomposition and synchronization
• A fast network-decomposition algorithm and its applications to constant-time distributed computation
• Sublinear fully distributed partition with applications
• Local mending
• Distributed strong diameter network decomposition
• A fast network-decomposition algorithm and its applications to constant-time distributed computation (extended abstract)
• Near-Linear Time Construction of Sparse Neighborhood Covers
• On the Complexity of Distributed Network Decomposition
• DECOMPOSITION ALGORITHMS TO COMPUTE THE QUICKEST TIME DISTRIBUTION IN DYNAMIC NETWORKS
• Network Decomposition and Distributed Derandomization (Invited Paper)
• Polylogarithmic-time deterministic network decomposition and distributed derandomization
• Fast network decomposition
• Distributed Strong Diameter Network Decomposition
• Improved network decompositions using small messages with applications on MIS, neighborhood covers, and beyond
• Faster deterministic distributed MIS and approximate matching
• About randomised distributed graph colouring and graph partition algorithms
• A faster distributed protocol for constructing a minimum spanning tree
• Fast deterministic distributed algorithms for sparse spanners

This page was built for publication: Fast distributed network decompositions and covers

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q676658)