Selection in the Presence of Memory Faults, with Applications to In-place Resilient Sorting

DOI10.1007/978-3-642-35261-4_58zbMath1260.68131arXiv1204.5229OpenAlexW1862384779MaRDI QIDQ4909572

Tsvi Kopelowitz, Nimrod Talmon

Publication date: 21 March 2013

Published in: Algorithms and Computation (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1204.5229

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Searching and sorting (68P10) Nonnumerical algorithms (68W05) Randomized algorithms (68W20)

Related Items

Resilient dynamic programming, Exploiting non-constant safe memory in resilient algorithms and data structures

Cites Work

• Unnamed Item
• Optimal resilient sorting and searching in the presence of memory faults
• Time bounds for selection
• Resilient \(k\)-d trees: \(k\)-means in space revisited
• Dynamic programming in faulty memory hierarchies (cache-obliviously)
• Resilient dictionaries
• Fault Tolerant External Memory Algorithms
• Optimal Resilient Dynamic Dictionaries
• Sorting and searching in the presence of memory faults (without redundancy)
• Priority Queues Resilient to Memory Faults
• Counting in the Presence of Memory Faults
• Lossless Fault-Tolerant Data Structures with Additive Overhead