The cost of unknown diameter in dynamic networks

DOI10.1145/3209665zbMATH Open1426.68228OpenAlexW2893438813WikidataQ129321778 ScholiaQ129321778MaRDI QIDQ4625652FDOQ4625652

Authors: Haifeng Yu, Yuda Zhao, Irvan Jahja 

Publication date: 25 February 2019

Published in: Journal of the ACM (Search for Journal in Brave)

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

Recommendations

• Networks cannot compute their diameter in sublinear time
• Some lower bounds in dynamic networks with oblivious adversaries
• Some lower bounds in dynamic networks with oblivious adversaries
• Distributed algorithms for network diameter and girth
• A note on hardness of diameter approximation

zbMATH Keywords

dynamic networkslower boundscommunication complexityunknown network diameter

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) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10)

Cited In (4)

• Networks cannot compute their diameter in sublinear time
• Sublinear algorithms in \(T\)-interval dynamic networks
• Some lower bounds in dynamic networks with oblivious adversaries
• Further optimizations of CSIDH: a systematic approach to efficient strategies, permutations, and bound vectors

This page was built for publication: The cost of unknown diameter in dynamic networks

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