آمار
| تعداد نشریات | 6 |
| تعداد شمارهها | 122 |
| تعداد مقالات | 1,551 |
| تعداد مشاهده مقاله | 1,649,924 |
| تعداد دریافت فایل اصل مقاله | 1,543,824 |
On the Covering Array Number of $3$-uniform Qualitative Independence Hypergraphs | ||
| Communications in Combinatorics and Optimization | ||
| مقالات آماده انتشار، پذیرفته شده، انتشار آنلاین از تاریخ 05 اردیبهشت 1405 اصل مقاله (510.83 K) | ||
| نوع مقاله: Original paper | ||
| شناسه دیجیتال (DOI): 10.22049/cco.2026.30424.2472 | ||
| نویسندگان | ||
| Raina Mary Thomas1؛ Yasmeen Akhtar* 2 | ||
| 1Department of Mathematics, Birla Institute of Technology and Science Pilani, K K Birla Goa Campus, Sancoale, Goa, India. | ||
| 2Department of Mathematics, Birla Institute of Technology and Science Pilani, K K Birla Goa Campus, Sancoale, Goa, India. | ||
| چکیده | ||
| Covering arrays (CAs) are widely recognized combinatorial designs that facilitate efficient test suite generation in software testing. For a positive integer $n$ and a set $S$ of size $g$, a \emph{covering array on a hypergraph} $H = (V, E)$ of size $n$ and alphabet size $g$, denoted $CA(n, H, g)$, is an $n \times |V|$ array with entries from $S$, where columns correspond to the vertices in $V$, such that for every hyperedge $e \in E$ of size $m$, the sub-array indexed by the vertices of $e$ contains all the ordered $m$-tuples from $S^m$ at least once, as a row. The smallest $n$ for which such an array exists is the \emph{covering array number of $H$}, denoted $CAN(H, g)$. This parameter represents the minimal test suite size for practical applications. For a $t$-uniform hypergraph $H$ and positive integers $g$ and $n$, a $CA(n, H, g)$ exists if and only if there is a hypergraph homomorphism from $H$ to $t\text{-}QI(n, g)$, a distinctive class of hypergraphs called \emph{qualitative independence hypergraphs}. Consequently, for such a hypergraph $H$, $CAN(H, g) \leq CAN(t\text{-}QI(n,g),g)$. In this paper, we develop a technique to determine the strong chromatic number and the size of the largest $3$-cliques of $3\text{-}QI(n, 2)$ to establish that $CAN(3\text{-}QI(n, 2),2)=n$ for some values of $n$ and apply the results obtained to find the covering array number of certain classes of hypergraphs. | ||
| کلیدواژهها | ||
| Qualitative Independence؛ Hypergraph؛ Covering Array؛ Software testing | ||
| مراجع | ||
|
[1] Y. Akhtar, A hyperedge coloring and application in combinatorial testing, AKCE Int. J. Graphs Comb. 19 (2022), no. 2, 125–132. https://doi.org/10.1080/09728600.2022.2081523
[2] Y. Akhtar and S. Maity, Mixed covering arrays on 3-uniform hypergraphs, Discrete Appl. Math. 232 (2017), 8–22. https://doi.org/10.1016/j.dam.2017.08.023 [3] Y. Akhtar and S. Maity, Covering array on the cartesian product of hypergraphs, Graphs Combin. 40 (2024), no. 4, Article number: 87 https://doi.org/10.1007/s00373-024-02813-5
[4] Y. Akhtar and F.K.H. Phoa, Cost-efficient mixed-level covering designs for testing experiments, J. Stat. Theory Pract. 14 (2020), Article number: 6 https://doi.org/10.1007/s42519-019-0062-7
[5] K.A. Bush, Orthogonal arrays of index unity, Ann. Math. Statist. 23 (1952), no. 3, 426–434. https://doi.org/10.1214/aoms/1177729387
[6] D.M. Cohen, S.R. Dalal, J. Parelius, and G.C. Patton, The combinatorial design approach to automatic test generation, IEEE software 13 (1996), no. 5, 83–88. https://doi.org/10.1109/52.536462
[7] C.J. Colbourn, CRC Handbook of Combinatorial Designs, CRC press, 2010.
[8] C.J. Colbourn, Covering array tables for $t = 2, 3, 4, 5, 6$, https://github.com/ugroempi/cas/blob/main/colbourntables.md, (2025).
[9] C.J. Colbourn, G. Kéri, P.P. Rivas Soriano, and J.-C. Schlage-Puchta, Covering and radius-covering arrays: Constructions and classification, Discrete Appl. Math. 158 (2010), no. 11, 1158–1180. https://doi.org/10.1016/j.dam.2010.03.008
[10] C.J. Colbourn, S.S. Martirosyan, T. Van Trung, and R.A. Walker, Roux-type constructions for covering arrays of strengths three and four, Des. Codes Crypt. 41 (2006), no. 1, 33–57. https://doi.org/10.1007/s10623-006-0020-8
[11] S.R. Dalal and C.L. Mallows, Factor-covering designs for testing software, Technometrics 40 (1998), no. 3, 234–243. https://doi.org/10.2307/1271179 [12] P. Erdos, C. Ko, and R. Rado, Intersection theorems for systems of finite sets, Quart. J. Math. Oxford Ser.(2) 12 (1961), 313–320. https://doi.org/10.1093/qmath/12.1.313
[13] A.S. Hedayat, N.J.A. Sloane, and J. Stufken, Orthogonal Arrays: Theory and Applications, Springer Science and Business Media, New York, 2012.
[14] I.S. Honkala, Modified bounds for covering codes, IEEE Trans. Info. Theory 37 (2006), no. 2, 351–365. https://doi.org/10.1109/18.75253
[15] K.A. Johnson and R. Entringer, Largest induced subgraphs of the n-cube that contain no 4-cycles, J. Combin. Theory Ser. B 46 (1989), no. 3, 346–355. https://doi.org/10.1016/0095-8956(89)90054-3
[16] L. Kampel and D.E. Simos, A survey on the state of the art of complexity problems for covering arrays, Theor. Comput. Sci. 800 (2019), 107–124. https://doi.org/10.1016/j.tcs.2019.10.019
[17] G.O. Katona, Two applications (for search theory and truth functions) of Spencer type theorems, Period. Math. Hungar. 3 (1973), no. 1, 19–26. https://doi.org/10.1007/BF02018457
[18] D.J. Kleitman and J. Spencer, Families of k-independent sets, Discrete Math. 6 (1973), no. 3, 255–262. https://doi.org/10.1016/0012-365X(73)90098-8 [19] J.I. Kokkala, K. Meagher, R. Naserasr, K.J. Nurmela, P.R. Östergård, and B. Stevens, On the structure of small strength-2 covering arrays, J. Combin. Des. 28 (2020), no. 1, 5–24. https://doi.org/10.1002/jcd.21671
[20] J. Korner and M. Lucertini, Compressing inconsistent data, IEEE Trans. Info. Theory 40 (2006), no. 3, 706–715. https://doi.org/10.1109/18.335882 [21] D.R. Kuhn, R.N. Kacker, and Y. Lei, Estimating t-way fault profile evolution during testing, IEEE 40th annual computer software and applications conference (COMPSAC), vol. 2, IEEE, 2016, pp. 596–597. https://doi.org/10.1109/COMPSAC.2016.110
[22] J. Lawrence, R.N. Kacker, Y. Lei, D.R. Kuhn, and M. Forbes, A survey of binary covering arrays, Electron. J. Comb. (2011), #P84. https://doi.org/10.37236/571
[23] X.N. Lu and M. Jimbo, Arrays for combinatorial interaction testing: A review on constructive approaches, Jpn. J. Stat. Data Sci. 2 (2019), 641–667. https://doi.org/10.1007/s42081-019-00056-w
[24] K. Meagher, Covering arrays on graphs: qualitative independence graphs and extremal set partition theory, Ph.D. thesis, Ottawa-Carleton Institute of Mathematics and Statistics, 2018.
[25] K. Meagher and B. Stevens, Covering arrays on graphs, J. Combin. Theory Ser. B 95 (2005), no. 1, 134–151. https://doi.org/10.1016/j.jctb.2005.03.005
[26] National Institute of Standards and Technology, The economic impacts of inadequate infrastructure for software testing, 2002.
[27] S. Raaphorst, Variable strength covering arrays, Ph.D. thesis, University of Ottawa (Canada), 2013.
[28] S. Raaphorst, L. Moura, and B. Stevens, Variable strength covering arrays, J. Combin. Des. 26 (2018), no. 9, 417–438. https://doi.org/10.1002/jcd.21602. [29] G. Seroussi and N.H. Bshouty, Vector sets for exhaustive testing of logic circuits, IEEE Trans. Info. Theory 34 (1988), no. 3, 513–522. https://doi.org/10.1109/18.6031
[30] B. Stevens and E. Mendelsohn, Efficient software testing protocols, Proceedings of the 1998 conference of the Centre for Advanced Studies on Collaborative research, 1998, p. 22.
[31] A.J. Tong, Y.G. Wu, and L.D. Li, Room-temperature phosphorimetry studies of some addictive drugs following dansyl chloride labelling, Talanta 43 (1996), no. 9, 1429–1436. https://doi.org/10.1016/0039-9140(96)01905-4
[32] J. Torres-Jimenez, I. Izquierdo-Marquez, and H. Avila-George, Methods to construct uniform covering arrays, IEEE Access 7 (2019), 42774–42797. https://doi.org/10.1109/ACCESS.2019.2907057
[33] W.D. Wallis and J.C. George, Introduction to Combinatorics, Chapman and Hall/CRC, New York, 2016.
[34] A.W. Williams and R.L. Probert, A practical strategy for testing pair-wise coverage of network interfaces, Proceedings of ISSRE’96: 7th International Symposium on Software Reliability Engineering, IEEE, 1996, pp. 246–254. | ||
|
آمار تعداد مشاهده مقاله: 41 تعداد دریافت فایل اصل مقاله: 26 |
||