New Upper Bounds for Covering Arrays of Order Seven

Jose Torres-Jimenez () and Idelfonso Izquierdo-Marquez
Additional contact information
Jose Torres-Jimenez: CINVESTAV-Tamaulipas, Cd. Victoria 87130, Tamaulipas, Mexico
Idelfonso Izquierdo-Marquez: CINVESTAV-Tamaulipas, Cd. Victoria 87130, Tamaulipas, Mexico

Mathematics, 2024, vol. 12, issue 12, 1-15

Abstract: A covering array is a combinatorial object that is used to test hardware and software components. The covering array number is the minimum number of rows needed to construct a specific covering array. The search for better upper bounds for covering array numbers is a very active area of research. Although there are many methods for defining new upper bounds for covering array numbers, recently the use of covering perfect hash families has significantly improved a large number of covering array numbers for alphabets that are prime powers. Currently, excellent upper bounds have been reported for alphabets 2, 3, 4, and 5; therefore, the focus of this article is on defining new upper bounds on the size of covering arrays for the alphabet seven using perfect hash families. For this purpose, a greedy column extension algorithm was constructed to increase the number of columns in a covering perfect hash family while keeping the number of rows constant. Our greedy algorithm begins with a random covering perfect hash family containing only eight columns and alternates between adding and removing columns. Adding columns increases the size of the covering perfect hash family while removing columns reduces the number of missing combinations in covering perfect hash families with different column counts. The construction process continues with the covering perfect hash family with the smallest number of columns being refined (i.e., missing combinations reduced). Thus, columns are dynamically added and removed to refine the covering perfect hash families being built. To illustrate the advantages of our greedy approach, 152 new covering perfect hash families of order seven with strengths 3, 4, 5, and 6 were constructed, enabling us to improve 12,556 upper bounds of covering array numbers; 903 of these improvements are for strength three, 8910 for strength four, 1957 for strength five, and 786 for strength six.

Keywords: covering perfect hash families; covering arrays; greedy algorithm (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2024
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/12/12/1908/pdf (application/pdf)
https://www.mdpi.com/2227-7390/12/12/1908/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:12:y:2024:i:12:p:1908-:d:1418626

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().