Mathematics – Combinatorics
Scientific paper
2011-11-02
Mathematics
Combinatorics
16 pages
Scientific paper
A $q$-ary $t$-covering array is an $m \times n$ matrix with entries from $\{0, 1, ..., 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 $m \times n$ 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.
Choi Soohak
Kim Hyun Kwang
Oh Dong Yeol
No associations
LandOfFree
Structures and lower bounds for binary covering arrays does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Structures and lower bounds for binary covering arrays, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Structures and lower bounds for binary covering arrays will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-329757