Braking the \(\Theta(n\log^ 2 n)\) barrier for sorting with faults

DOI10.1006/jcss.1997.1470zbMath0872.68033OpenAlexW2016350196MaRDI QIDQ1356885

C. Greg Plaxton, Yuan Ma, Leighton, Tom

Publication date: 3 August 1997

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1006/jcss.1997.1470

zbMATH Keywords

networksparallel algorithmsfault-tolerant sorting circuits

Mathematics Subject Classification ID

Searching and sorting (68P10) Information storage and retrieval of data (68P20)

Related Items (7)

External-memory sorting with comparison errors ⋮ Recursive merge sort with erroneous comparisons ⋮ Designing reliable algorithms in unreliable memories ⋮ Resilient dynamic programming ⋮ Sorting and searching in faulty memories ⋮ The price of resiliency: a case study on sorting with memory faults ⋮ Optimal resilient sorting and searching in the presence of memory faults

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Improved sorting networks with O(log N) depth
• Sorting in \(c \log n\) parallel steps
• Ramanujan graphs
• On the design of reliable Boolean circuits that contain partially unreliable gates
• A Correction Network for N-Sorters
• Tight Bounds on the Complexity of Parallel Sorting
• On Fault-Tolerant Networks for Sorting
• Fault Tolerant Sorting Networks
• Tight Bounds on the Size of Fault-Tolerant Merging and Sorting Networks with Destructive Faults
• Reliable minimum finding comparator networks

This page was built for publication: Braking the \(\Theta(n\log^ 2 n)\) barrier for sorting with faults