The MathNet Korea
Information Center for Mathematical Science

논문검색

Information Center for Mathematical Science

논문검색

SIAM Journal on Computing
( Vol. 29 NO.1 / (1999))
Tight Bounds on the Size of Fault-Tolerant Merging and Sorting Networks with Destructive Faults
Tom Leighton, Yuan Ma,
Pages. 258-273
Abstract
Contents 1. Introduction 2. The lower bound on size for worst-case faults 3. The lower
bound on size for random faults 4. Trading depth for width 5.
Concluding remarks
Key words merging, sorting, circuits, comparator networks, fault-tolerance, lower bounds, probabilistic analysis of algorithms
Mathmatical Subject Classification 68Q22, 68Q25, 94C99