×

Covering and radius-covering arrays: constructions and classification. (English) Zbl 1231.05033

Summary: 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.

MSC:

05B15 Orthogonal arrays, Latin squares, Room squares
68R10 Graph theory (including graph drawing) in computer science
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] O. Bakun, Local optimization search for covering arrays, Private communication by email, August 2009.; O. Bakun, Local optimization search for covering arrays, Private communication by email, August 2009.
[2] Bhandari, M. C.; Durairajan, C., A note on bounds for \(q\)-ary covering codes, IEEE Trans. Inform. Theory, 42, 1640-1642 (1996) · Zbl 0857.94024
[3] Bierbrauer, J., Bounds on orthogonal arrays and resilient functions, J. Combin. Des., 3, 179-183 (1995) · Zbl 0886.05034
[4] Bollobás, B., Sperner systems consisting of pairs of complementary subsets, J. Combin. Theory Ser. A, 15, 363-366 (1973) · Zbl 0281.05001
[5] Bose, R. C., Mathematical theory of the symmetric factorial design, Sankhyā, 8, 107-166 (1947) · Zbl 0038.09601
[6] A. Brace, D.E. Daykin, Sperner type theorems for finite sets, in: D.J.A. Welsh and D. R. Woodall (Eds.), Combinatorics (Proc. Conf. Combinatorial Math., Math. Inst., Oxford), Inst. Math. Appl., Southend-on-Sea, 1972, pp. 18-37.; A. Brace, D.E. Daykin, Sperner type theorems for finite sets, in: D.J.A. Welsh and D. R. Woodall (Eds.), Combinatorics (Proc. Conf. Combinatorial Math., Math. Inst., Oxford), Inst. Math. Appl., Southend-on-Sea, 1972, pp. 18-37.
[7] Bryce, R. C.; Colbourn, C. J., A density-based greedy algorithm for higher strength covering arrays, Softw. Test. Verif. Reliab., 19, 37-53 (2009)
[8] Bush, K. A., Orthogonal arrays of index unity, Ann. Math. Statist., 23, 426-434 (1952) · Zbl 0047.01704
[9] Chateauneuf, M.; Kreher, D. L., On the state of strength-three covering arrays, J. Combin. Des., 10, 217-238 (2002) · Zbl 1003.05022
[10] Cohen, G.; Honkala, I.; Litsyn, S.; Lobstein, A., Covering Codes (1997), Elsevier: Elsevier Amsterdam · Zbl 0874.94001
[11] M.B. Cohen, Designing test suites for software interaction testing, Ph.D. Thesis, The University of Auckland, Department of Computer Science, 2004.; M.B. Cohen, Designing test suites for software interaction testing, Ph.D. Thesis, The University of Auckland, Department of Computer Science, 2004.
[12] Colbourn, C. J., Combinatorial aspects of covering arrays, Matematiche (Catania), 58, 121-167 (2004)
[13] Colbourn, C. J., Strength two covering arrays: existence tables and projection, Discrete Math., 308, 772-786 (2008) · Zbl 1134.05013
[14] C.J. Colbourn, Covering array tables 2005-present, http://www.public.asu.edu/ ccolbou/src/tabby/catable.html; C.J. Colbourn, Covering array tables 2005-present, http://www.public.asu.edu/ ccolbou/src/tabby/catable.html
[15] Colbourn, C. J., Covering arrays from cyclotomy, Des. Codes Cryptogr., 55, 201-219 (2010) · Zbl 1215.05019
[16] Colbourn, C. J.; Kéri, G., Covering arrays and existentially closed graphs, Lect. Notes Comput. Sci., 5557, 22-33 (2009) · Zbl 1248.05034
[17] Dembowski, P., Finite Geometries (1968), Springer: Springer Berlin · Zbl 0159.50001
[18] Forbes, M.; Lawrence, J.; Lei, Y.; Kacker, R. N.; Kuhn, D. R., Refining the in-parameter-order strategy for constructing covering arrays, J. Res. Nat. Inst. Stand. Tech., 113, 287-297 (2008)
[19] Füredi, Z., A projective plane is an outstanding 2-cover, Discrete Math., 74, 321-324 (1989) · Zbl 0732.05019
[20] W. Haas, J. Quistorff, J.-C. Schlage-Puchta, New lower bounds for covering codes, manuscript.; W. Haas, J. Quistorff, J.-C. Schlage-Puchta, New lower bounds for covering codes, manuscript.
[21] Hartman, A., Software and hardware testing using combinatorial covering suites, (Golumbic, M. C.; Hartman, I. B.A., Interdisciplinary Applications of Graph Theory, Combinatorics, and Algorithms (2005), Springer: Springer Norwell, MA), 237-266 · Zbl 1089.68023
[22] Hedayat, A. S.; Sloane, N. J.A.; Stufken, J., Orthogonal Arrays (1999), Springer-Verlag: Springer-Verlag New York · Zbl 0935.05001
[23] Hnich, B.; Prestwich, S.; Selensky, E.; Smith, B. M., Constraint models for the covering test problem, Constraints, 11, 199-219 (2006) · Zbl 1103.68810
[24] Johnson, K. A.; Entringer, R., Largest induced subgraphs of the \(n\)-cube that contain no 4-cycles, J. Combin. Theory Ser. B, 46, 346-355 (1989) · Zbl 0626.05029
[25] Katona, G. O.H., Two applications (for search theory and truth functions) of Sperner type theorems, Period. Math. Hungar., 3, 19-26 (1973) · Zbl 0266.05001
[26] Kéri, G.; Östergård, P. R.J., On the covering radius of small codes, Studia Sci. Math. Hungar., 40, 243-256 (2003) · Zbl 1027.94043
[27] Kéri, G.; Östergård, P. R.J., Bounds for covering codes over large alphabets, Des. Codes Cryptogr., 137, 45-60 (2005) · Zbl 1158.94424
[28] Kéri, G.; Östergård, P. R.J., The number of inequivalent \((2 R + 3, 7) R\) optimal covering codes, J. Integer Seq., 9 (2006), Article 06.4.7 (electronic) · Zbl 1027.94043
[29] Kéri, G.; Östergård, P. R.J., Further results on the covering radius of small codes, Discrete Math., 307, 69-77 (2007) · Zbl 1278.94098
[30] Kleitman, D. J.; Spencer, J., Families of \(k\)-independent sets, Discrete Math., 6, 255-262 (1973) · Zbl 0269.05002
[31] Kounias, S.; Petros, C. I., Orthogonal arrays of strength three and four with index unity, Sankhyā B, 37, 228-240 (1975) · Zbl 0342.05014
[32] Li, Y.; Ji, L.; Yin, J. X., Covering arrays of strength 3 and 4 from holey difference matrices, Des. Codes Cryptogr., 50, 339-350 (2009) · Zbl 1247.05042
[33] D. Linnemann, M. Frewer, Computations with the density algorithm, private communication by email, October 2008.; D. Linnemann, M. Frewer, Computations with the density algorithm, private communication by email, October 2008.
[34] J. Lobb, 2007 private communication.; J. Lobb, 2007 private communication.
[35] MacWilliams, F. J.; Sloane, N. J.A., The Theory of Error-Correcting Codes (1977), North-Holland Publishing Company: North-Holland Publishing Company Amsterdam · Zbl 0369.94008
[36] McEliece, R. J.; Rodemich, E. R.; Rumsey, H.; Welch, L. R., New upper bounds on the rate of a code via the Delsarte-MacWilliams inequalities, IEEE Trans. Inform. Theory, 23, 157-166 (1977) · Zbl 0361.94016
[37] Meagher, K.; Stevens, B., Group construction of covering arrays, J. Combin. Des., 13, 70-77 (2005) · Zbl 1057.05023
[38] Nayeri, P.; Colbourn, C. J.; Konjevod, G., Randomized postoptimization of covering arrays, Lect. Notes Comput. Sci., 5874, 408-419 (2009) · Zbl 1267.05051
[39] Nurmela, K. J., Upper bounds for covering arrays by tabu search, Discrete Appl. Math., 138, 143-152 (2004) · Zbl 1034.05013
[40] Östergård, P. R.J.; Weakley, W. D., Classification of binary covering codes, J. Combin. Des., 8, 391-401 (2000) · Zbl 0989.94037
[41] J. Quistorff, J.-C. Schlage-Puchta, On generalized surjective codes, Studia Sci. Math. Hungar. (in press).; J. Quistorff, J.-C. Schlage-Puchta, On generalized surjective codes, Studia Sci. Math. Hungar. (in press).
[42] L. Rouse-Lamarre, Tabu search for covering arrays, Private communication by email, April 2009.; L. Rouse-Lamarre, Tabu search for covering arrays, Private communication by email, April 2009.
[43] Sherwood, G. B.; Martirosyan, S. S.; Colbourn, C. J., Covering arrays of higher strength from permutation vectors, J. Combin. Des., 14, 202-213 (2006) · Zbl 1092.05010
[44] Sloane, N. J.A., Covering arrays and intersecting codes, J. Combin. Des., 1, 51-63 (1993) · Zbl 0828.05023
[45] B. Stevens, Transversal covers and packings, Ph.D. Thesis, Mathematics, University of Toronto, 1998.; B. Stevens, Transversal covers and packings, Ph.D. Thesis, Mathematics, University of Toronto, 1998.
[46] Stevens, B.; Moura, L.; Mendelsohn, E., Lower bounds for transversal covers, Des. Codes Cryptogr., 15, 279-299 (1998) · Zbl 0924.05009
[47] Tarry, G., Le problème de 36 officiers, Assoc. Franc. Av. Sci., 29, 170-203 (1900) · JFM 32.0219.04
[48] J. Torres-Jimenez, E. Rodriguez-Tello, Simulated annealing for constructing binary covering arrays of strength four, preprint, 2009.; J. Torres-Jimenez, E. Rodriguez-Tello, Simulated annealing for constructing binary covering arrays of strength four, preprint, 2009.
[49] Walker II, R. A.; Colbourn, C. J., Tabu search for covering arrays using permutation vectors, J. Stat. Plann. Infererence, 139, 69-80 (2009) · Zbl 1284.62497
[50] M. Younis, MIPOG: a search strategy for test suites, private communication, 2009.; M. Younis, MIPOG: a search strategy for test suites, private communication, 2009.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.