The bit complexity of the predecessor problem

DOI10.1016/S0020-0190(97)00094-XMaRDI QIDQ287147zbMATHOpenAlexFDO

Authors Yehuda Afek, M. Cohen, E. Haalman

Publication date 26 May 2016

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0020-0190(97)00094-x

zbMATH Keywords

distributed computinganonymous ringunidirectional

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10)

Recommendations

• Optimal bounds for the predecessor problem and related problems
• Optimal bounds for the predecessor problem
• Lower bounds for predecessor searching in the cell probe model
• Tight bounds for synchronous communication of information using bits and silence
• Time-space trade-offs for predecessor search

Cites work

• scientific article; zbMATH DE number 871956 (Why is no real title available?)
• Complexity of network synchronization
• Distributed Algorithms For Unidirectional Networks
• Electing a leader in a synchronous ring
• The firing squad synchronization problem for graphs

This page was built for publication: The bit complexity of the predecessor problem

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