×

Covering arrays on product graphs. (English) Zbl 1371.05224

Summary: Two vectors \(x\), \(y\) in \(\mathbb {Z}_g^n\) are qualitatively independent if for all pairs \((a,b)\in \mathbb {Z}_g\times \mathbb {Z}_g\), there exists \(i\in \{1,2,\dots,n\}\) such that \((x_i,y_i)=(a,b)\). A covering array on a graph \(G\), denoted by \(\mathrm{CA}(n,G,g)\), is a \(|V(G)|\times n\) array on \(\mathbb {Z}_g\) with the property that any two rows which correspond to adjacent vertices in \(G\) are qualitatively independent. The number of columns in such array is called its size. Given a graph \(G\), a covering array on \(G\) with minimum size is called optimal. Our primary concern in this paper is with constructions that make optimal covering arrays on large graphs that are obtained from product of smaller graphs. We consider four most extensively studied graph products in the literature and give upper and lower bounds on the size of covering arrays on product graphs. We find families of graphs for which the size of covering array on the Cartesian product graphs achieves the lower bound. Finally, we present a polynomial time approximation algorithm with approximation ratio \(\left\lceil \log (\frac{|V|}{2^{k-1}})\right\rceil \) for constructing covering array on graph \(G=(V,E)\) with \(k>1\) prime factors with respect to the Cartesian product.

MSC:

05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C76 Graph operations (line graphs, products, etc.)
05C85 Graph algorithms (graph-theoretic aspects)
05C25 Graphs and abstract algebra (groups, rings, fields, etc.)
05C75 Structural characterization of families of graphs

Software:

AETG
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Bush, K.A.: A generalization of the theorem due to MacNeish. Ann. Math. Stat. 23, 293-295 (1952) · Zbl 0047.01702 · doi:10.1214/aoms/1177729449
[2] Bush, K.A.: Orthogonal arrays of index unity. Ann. Math. Stat. 23, 426-434 (1952) · Zbl 0047.01704 · doi:10.1214/aoms/1177729387
[3] Chateauneuf, M.A., Colbourn, C.J., Kreher, D.L.: Covering arrays of strength three. Des. Codes. Cryptogr. 16(1), 235-242 (1999) · Zbl 0938.05017 · doi:10.1023/A:1008379710317
[4] Cheng, C., Dumitrescu, A., Schroeder, P.: Generating small combinatorial test suites to cover input-output relationships. In: Proc. 3rd Intern. Conference on Quality Software, pp. 76-82 (2003) · Zbl 1134.05306
[5] Cohen, D.M., Dalal, S.R., Fredman, M.L., Patton, G.C.: The AETG system: an approach to testing based on combinatorial design. IEEE Trans. Softw. Eng. 23(7), 437-443 (1997) · doi:10.1109/32.605761
[6] Colbourn, C.J., Martirosyan, S.S., Mullen, G.L., Shasha, D.E., Sherwood, G.B., Yucas, J.L.: Products of mixed covering arrays of strength two. J. Combin. Des. 14, 124-138 (2006) · Zbl 1134.05306 · doi:10.1002/jcd.20065
[7] Olbourn, C.J., Dinitz, J.H.: Handbook of Combinatorial Design. CRC Press, Boca Raton (1996) · Zbl 0836.00010 · doi:10.1201/9781420049954
[8] Hammack, R., Imrich, W., Klavžar, S.: Hand Book of Product Graphs, 2nd edn. CRC Press, Boca Raton (2011) · Zbl 1283.05001
[9] Hammack, R., Imrich, W.: On Cartesian skeletons of graphs. Ars Math. Contemp. 2(2), 191-205 (2009) · Zbl 1190.05099
[10] Hartman, A., Raskin, L.: Problems and algorithms for covering arrays. Discret. Math. 284, 149-156 (2004) · Zbl 1044.05029 · doi:10.1016/j.disc.2003.11.029
[11] Hellmuth, H.: A local prime factor decomposition algorithm. Discret. Math. 311(12), 944-965 (2011) · Zbl 1223.05230 · doi:10.1016/j.disc.2011.02.016
[12] Hell, P., Nešetřil, J.: Graphs and Homomorphisms. Oxford University Press, Oxford (2004) · Zbl 1062.05139 · doi:10.1093/acprof:oso/9780198528173.001.0001
[13] Kleitman, D.J., Spencer, J.: Families of \[k\] k-independent sets. Discret. Math. 6, 255-262 (1973) · Zbl 0269.05002 · doi:10.1016/0012-365X(73)90098-8
[14] Korner, J., Lucertini, M.: Compressing inconsistent data. IEEE Trans. Inf. Theory 40(3), 706-715 (1994) · Zbl 0939.68509 · doi:10.1109/18.335882
[15] Meagher, K., Moura, L., Zekaoui, L.: Mixed covering arrays on Graphs. J. Combin. Des. 15, 393-404 (2007) · Zbl 1137.05016 · doi:10.1002/jcd.20149
[16] Meagher, K., Stevens, B.: Covering arrays on graphs. J. Combin. Theory. Ser. B 95, 134-151 (2005) · Zbl 1074.05021 · doi:10.1016/j.jctb.2005.03.005
[17] Moura, L., Stardom, J., Stevens, B., Williams, A.: Covering arrays with mixed alphabet sizes. J. Combin. Des. 11, 413-432 (2003) · Zbl 1031.05027 · doi:10.1002/jcd.10059
[18] Riesel, H.: Prime Numbers and Computer Methods for Factorisation, Progress in Mathematics, vol. 57. Springer, New York (1985) · Zbl 0582.10001 · doi:10.1007/978-1-4757-1089-2
[19] Sabidussi, G.: Graph multiplication. Math. Z. 72, 446-457 (1960) · Zbl 0093.37603 · doi:10.1007/BF01162967
[20] Sabidussi, G.: Graphs with given group and given graph-theoretical properties. Can. J. Math. 9, 515-525 (1957) · Zbl 0079.39202 · doi:10.4153/CJM-1957-060-7
[21] Seroussi, G., Bshouty, N.H.: Vector sets for exhaustive testing of logic circuits. IEEE Trans. Inf. Theory 34, 513-522 (1988) · Zbl 0653.94025 · doi:10.1109/18.6031
[22] Sloane, N.J.A.: Covering arrays and intersecting codes. J. Combin. Des. 1, 51-63 (1993) · Zbl 0828.05023 · doi:10.1002/jcd.3180010106
[23] Stevens, B.: Transversal covers and packings, PhD Thesis, University of Toronto, Toronto (1998)
[24] Stevens, B., Ling, A., Mendelsohn, E.: A direct constriction of transversal covers using group divisible designs. Ars Combin. 63, 145-159 (2002) · Zbl 1076.05502
[25] Vizing, V.G.: The Cartesian product of graphs, Vyčisl. Sistemy 9, 30-43 (1963) · Zbl 0194.25203
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.