Fast network decomposition

DOI10.1145/135419.135456MaRDI QIDQ5348849zbMATH OpenOpenAlexFDO

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

Publication date 21 August 2017

Published in Proceedings of the eleventh annual ACM symposium on Principles of distributed computing - PODC '92 (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/135419.135456

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Distributed algorithms (68W15)

Recommendations

• Faster network algorithms based on graph decomposition
• A fast network-decomposition algorithm and its applications to constant-time distributed computation (extended abstract)
• Fast distributed network decompositions and covers
• A fast network-decomposition algorithm and its applications to constant-time distributed computation
• scientific article; zbMATH DE number 3860397
• A new approach to network decomposition problems
• Optimal Decomposition of Large-Scale Networks
• Faster algorithms for shortest path and network flow based on graph decomposition
• On the Complexity of Distributed Network Decomposition
• DECOMPOSITION ALGORITHMS TO COMPUTE THE QUICKEST TIME DISTRIBUTION IN DYNAMIC NETWORKS

Cited in

(16)

• Graph theoretical issues in computer networks
• Simple and efficient network decomposition and synchronization
• A fast network-decomposition algorithm and its applications to constant-time distributed computation
• Distributed strong diameter network decomposition
• A fast network-decomposition algorithm and its applications to constant-time distributed computation (extended abstract)
• Distributed Disaster Disclosure
• Near-Linear Time Construction of Sparse Neighborhood Covers
• Generating sparse 2—spanners
• Low-diameter graph decomposition is in NC
• DECOMPOSITION ALGORITHMS TO COMPUTE THE QUICKEST TIME DISTRIBUTION IN DYNAMIC NETWORKS
• Distributed distance-r covering problems on sparse high-girth graphs
• Distributed distance-\(r\) covering problems on sparse high-girth graphs
• Improved network decompositions using small messages with applications on MIS, neighborhood covers, and beyond
• Fast distributed network decompositions and covers
• Negative-weight single-source shortest paths in near-linear time
• Near-optimal directed low-diameter decompositions

This page was built for publication: Fast network decomposition

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