Filling logarithmic gaps in distributed complexity for global problems

DOI10.1007/978-3-662-46078-8_31MaRDI QIDQ5175124zbMATH OpenOpenAlexFDO

Authors Hiroaki Ookawa, Taisuke Izumi

Publication date 20 February 2015

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-662-46078-8_31

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Distributed algorithms (68W15) Communication complexity, information complexity (68Q11)

Recommendations

• A near-tight lower bound on the time complexity of distributed minimum-weight spanning tree construction
• The lower bounds on distributed shortest paths
• Distributed MST for constant diameter graphs
• The distributed minimum spanning tree problem

Cited in

(2)

• Low-congestion shortcut and graph parameters
• Sparsifying congested cliques and core-periphery networks

This page was built for publication: Filling logarithmic gaps in distributed complexity for global problems

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