Tight Bounds on the Size of Fault-Tolerant Merging and Sorting Networks with Destructive Faults

DOI10.1137/S0097539796305298zbMath0937.68159MaRDI QIDQ4268879

Leighton, Tom, Yuan Ma

Publication date: 28 October 1999

Published in: SIAM Journal on Computing (Search for Journal in Brave)

zbMATH Keywords

sorting; lower bounds; circuits; fault-tolerance; probabilistic analysis of algorithms; merging; comparator networks

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68W10: Parallel algorithms in computer science

94C99: Circuits, networks

Related Items

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