Optimal resilient sorting and searching in the presence of memory faults
From MaRDI portal
Publication:1035681
DOI10.1016/j.tcs.2009.07.026zbMath1183.68230OpenAlexW2058699483WikidataQ61609530 ScholiaQ61609530MaRDI QIDQ1035681
Irene Finocchi, Giuseppe F. Italiano, Fabrizio Grandoni
Publication date: 4 November 2009
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2009.07.026
sortingsearchingcombinatorial algorithmsmemory modelsmemory faultscomputing with unreliable information
Related Items
Resilient level ancestor, bottleneck, and lowest common ancestor queries in dynamic trees ⋮ Recursive merge sort with erroneous comparisons ⋮ Selection in the Presence of Memory Faults, with Applications to In-place Resilient Sorting ⋮ Resilient dynamic programming ⋮ Resilient Dictionaries for Randomly Unreliable Memory ⋮ Approximate minimum selection with unreliable comparisons ⋮ Exploiting non-constant safe memory in resilient algorithms and data structures ⋮ On the error resilience of ordered binary decision diagrams
Cites Work
- Coping with errors in binary search procedures
- Braking the \(\Theta(n\log^ 2 n)\) barrier for sorting with faults
- On Fault-Tolerant Networks for Sorting
- Optimal Resilient Dynamic Dictionaries
- Sorting and searching in the presence of memory faults (without redundancy)
- Fault Tolerant Sorting Networks
- Tight Bounds on the Size of Fault-Tolerant Merging and Sorting Networks with Destructive Faults
- Computing with Noisy Information
- On word-level parallelism in fault-tolerant computing
- Comparison-based search in the presence of errors
- The Price of Resiliency: A Case Study on Sorting with Memory Faults
- Automata, Languages and Programming
- Algorithms – ESA 2005
- Computer Aided Verification
- Searching games with errors -- fifty years of coping with liars
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
