Distributed MST for constant diameter graphs

DOI10.1145/383962.383984MaRDI QIDQ5890494zbMATH OpenOpenAlexFDO

Authors Zvi Lotker, Boaz Patt-Shamir, David Peleg

Publication date 4 March 2016

Published in Proceedings of the twentieth annual ACM symposium on Principles of distributed computing (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Distance in graphs (05C12) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Distributed algorithms (68W15)

Recommendations

• Distributed MST for constant diameter graphs
• A Local Distributed Algorithm to Approximate MST in Unit Disc Graphs
• Distributed MST and routing in almost mixing time
• Distributed algorithms for network diameter and girth
• Constant-time distributed dominating set approximation
• Constant-time distributed dominating set approximation
• Distributed Approximation Algorithms in Unit-Disk Graphs
• Distributed algorithms for random graphs

Cited in

(8)

• A distributed algorithm for constructing a minimum diameter spanning tree
• Latency, capacity, and distributed minimum spanning trees
• Distributed maximum maintenance on hierarchically divided graphs
• Sparsifying congested cliques and core-periphery networks
• Hundreds of impossibility results for distributed computing
• Networks cannot compute their diameter in sublinear time
• Distributed MST for constant diameter graphs
• Fast deterministic distributed algorithms for sparse spanners

This page was built for publication: Distributed MST for constant diameter graphs

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