The cost of unknown diameter in dynamic networks

DOI10.1145/3209665MaRDI QIDQ4625652zbMATHOpenAlexWikidataFDO

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

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)

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

Cited in

(4)

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

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)