Structures and lower bounds for binary covering arrays

DOI10.1016/J.DISC.2012.06.013MaRDI QIDQ449145zbMATH OpenOpenAlexFDO

Authors Soohak Choi, Hyun Kwang Kim, Dong Yeol Oh

Publication date 12 September 2012

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1111.0587

zbMATH Keywords

covering arraysRoux's boundErdős-Ko-Rado theorem

Mathematics Subject Classification ID

Orthogonal arrays, Latin squares, Room squares (05B15) Combinatorial aspects of packing and covering (05B40)

Abstract: A $q$-ary $t$-covering array is an $mimesn$ matrix with entries from $0,1,\mathrm{...},q-1$ with the property that for any $t$ column positions, all $q^t$ possible vectors of length $t$ occur at least once. One wishes to minimize $m$ for given $t$ and $n$, or maximize $n$ for given $t$ and $m$. For $t=2$ and $q=2$, it is completely solved by R'enyi, Katona, and Kleitman and Spencer. They also show that maximal binary 2-covering arrays are uniquely determined. Roux found the lower bound of $m$ for a general $t,n$, and $q$. In this article, we show that $mimesn$ binary 2-covering arrays under some constraints on $m$ and $n$ come from the maximal covering arrays. We also improve the lower bound of Roux for $t=3$ and $q=2$, and show that some binary 3 or 4-covering arrays are uniquely determined.

Recommendations

• A survey of binary covering arrays
• t-Covering Arrays: Upper Bounds and Poisson Approximations
• Covering arrays and intersecting codes
• Binary consecutive covering arrays
• On the state of strength-three covering arrays

Cites work

• scientific article; zbMATH DE number 1286223 (Why is no real title available?)
• scientific article; zbMATH DE number 1559534 (Why is no real title available?)
• scientific article; zbMATH DE number 1759800 (Why is no real title available?)
• scientific article; zbMATH DE number 1775428 (Why is no real title available?)
• scientific article; zbMATH DE number 867473 (Why is no real title available?)
• scientific article; zbMATH DE number 5171518 (Why is no real title available?)
• A classification of the structures of some Sperner families and superimposed codes
• A course in combinatorics.
• Covering and radius-covering arrays: constructions and classification
• Covering arrays and intersecting codes
• Families of \(k\)-independent sets
• INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
• Intersecting codes and independent families
• Largest induced subgraphs of the n-cube that contain no 4-cycles
• Lower bounds for transversal covers
• Oblivious transfers and intersecting codes
• On Representatives of Subsets
• SOME INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
• Subquadratic zero-knowledge
• Two applications (for search theory and truth functions) of Sperner type theorems
• Universal classes of hash functions
• Upper bounds for covering arrays by tabu search.

Cited in

(9)

• Arrays for combinatorial interaction testing: a review on constructive approaches
• New optimal covering arrays using an orderly algorithm
• Binary Covering Arrays and Existentially Closed Graphs
• A survey of binary covering arrays
• Disjoint Covers in Replicated Heterogeneous Arrays
• Optimum super-simple mixed covering arrays of type \(a^1 b^{k-1}\)
• Perfect sets of paths in the full graph of SDN switches
• Binary consecutive covering arrays
• New covering array numbers

Describes a project that uses

Uses Software

• AETG

This page was built for publication: Structures and lower bounds for binary covering arrays

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q449145)