|
|||||
|
|
Covering and radius-covering arrays: Constructions and classification |
|
| Authors: | C.J. Colbourn P.P. Rivas Soriano |
| Affiliation: | a Computer Science and Engineering, Arizona State University, P.O. Box 878809, Tempe, AZ 85287, USA b Computer and Automation Research Institute, Hungarian Academy of Sciences, H-1111 Budapest Kende utca 13-17, Hungary c C/ Padre Astete, 18, 4° G, 37004 Salamanca, Spain d Department of Pure Mathematics and Computer Algebra, Ghent University, Building S22 Krijgslaan 281, 9000 Gent, Belgium |
| Abstract: | The minimum number of rows in covering arrays (equivalently, surjective codes) and radius-covering arrays (equivalently, surjective codes with a radius) has been determined precisely only in special cases. In this paper, explicit constructions for numerous best known covering arrays (upper bounds) are found by a combination of combinatorial and computational methods. For radius-covering arrays, explicit constructions from covering codes are developed. Lower bounds are improved upon using connections to orthogonal arrays, partition matrices, and covering codes, and in specific cases by computation. Consequently for some parameter sets the minimum size of a covering array is determined precisely. For some of these, a complete classification of all inequivalent covering arrays is determined, again using computational techniques. Existence tables for up to 10 columns, up to 8 symbols, and all possible strengths are presented to report the best current lower and upper bounds, and classifications of inequivalent arrays. |
| Keywords: | Covering array Surjective code Simulated annealing Symbol fusion Classification of codes Partition matrix |
| 本文献已被 ScienceDirect 等数据库收录！ | |