Optimal conclusive sets for comparator networks |
| |
Authors: | Guy Even Tamir Levi Ami Litman |
| |
Affiliation: | 1. School of Electrical Engineering, Tel-Aviv University, Tel-Aviv 69978, Israel;2. Faculty of Computer Science, Technion, Haifa 32000, Israel |
| |
Abstract: | A set of input vectors S is conclusive for a certain functionality if, for every comparator network, correct functionality for all input vectors is implied by correct functionality for all vectors in S. We consider four functionalities of comparator networks: sorting, merging, sorting of bitonic vectors, and halving. For each of these functionalities, we present two conclusive sets of minimal cardinality. The members of the first set are restricted to be binary, while the members of the second set are unrestricted. For all the above functionalities, except halving, the unrestricted conclusive set is much smaller than the binary one. |
| |
Keywords: | Zero&ndash one Principle Comparator networks Sorting networks Bitonic sorting Merging networks |
本文献已被 ScienceDirect 等数据库收录! |
|