Bounds on the size of test sets for sorting and related networks

DOI10.1016/0012-365X(90)90173-FzbMath0695.68034MaRDI QIDQ910215

Moon Jung Chung, Bala Ravikumar

Publication date: 1990

Published in: Discrete Mathematics (Search for Journal in Brave)

zbMATH Keywords

selectortest setsorting networkmodels of computationmerging network

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Searching and sorting (68P10)

Related Items (5)

Bounds on the size of merging networks ⋮ Optimal-depth sorting networks ⋮ Formally proving size optimality of sorting networks ⋮ Sorting nine inputs requires twenty-five comparisons ⋮ Strong nondeterministic Turing reduction - a technique for proving intractability

Cites Work

• Sorting in \(c \log n\) parallel steps
• Sorting by means of swappings
• On the Number of Stable States in a NOR Network
• Unnamed Item

This page was built for publication: Bounds on the size of test sets for sorting and related networks