 Home Research - Covering Arrays |
October 03, 2023 |
Introduction
This web page aims at reporting the main results produced during the project No. 099276, entitled "Algorithms for the canonization of Covering Arrays" (2010-2014), funded by the CONACyT Mexico.
The main objective of this project was designing and implementing efficient algorithms, both exact and approximate ones, for the canonization of Covering Arrays (CA's).
A covering array, CA(N; t, k, v), of size N, strength t, degree k, and order v is an N × k array on v symbols such that every N × t sub-array includes, at least once, all the ordered subsets from v symbols of size t (t-tuples). The minimum N for which a CA(N; t, k, v) exists is the covering array number and it is defined according to the following equation.
Finding the covering array number is also known in the literature as the Covering Array Construction (CAC) problem. It is equivalent to the problem of maximizing the degree k of a covering array given the values N, t, and v. Addressing this problem in reasonable time has been the focus of much research.
Relevant publications
| New Bounds for Binary Covering Arrays Using Simulated Annealing. Jose Torres-Jimenez and Eduardo Rodriguez-Tello, Information Sciences, 185(1):137-152, Elsevier February 2012. |
 |
 |
| Simulated Annealing for Constructing Binary Covering Arrays of
Variable Strength. Jose Torres-Jimenez and Eduardo Rodriguez-Tello, Proceedings of the IEEE CEC 2010, Barcelona Spain, pp. 4102-4109, IEEE Press 2010. |
|
|
| Memetic Algorithms for Constructing Binary Covering Arrays of Strength Three. Eduardo Rodriguez-Tello and Jose Torres-Jimenez, Proceedings of the EA 2009, Strasbourg France, Lecture Notes in Computer Science, 5975:86-97, Springer 2010. 2nd place Best Paper Award |
|
|
| A New Backtracking Algorithm for Constructing Binary Covering Arrays of Variable Strength. Josue Bracho-Rios, Jose Torres-Jimenez and Eduardo Rodriguez-Tello, Proceedings of the MICAI 2009, Guanajuato, México, Lecture Notes in Artificial Intelligence, 5845:397-407, Springer 2009. |
|
|
| Strength Two Covering Arrays Construction Using a SAT Representation. Daniel Lopez-Escogido, Jose Torres-Jimenez, Eduardo Rodriguez-Tello and Nelson Rangel-Valdez, Proceedings of the MICAI 2008, Edo. Méx. México, Lecture Notes in Artificial Intelligence, 5317:44-53, Springer 2008. |
|
|
Use of Covering Arrays for tunning metaheuristics
| Maximum Parsimony Phylogenetic Inference Using Simulated Annealing. Jean-Michel Richer, Eduardo Rodriguez-Tello and Karla E. Vazquez-Ortiz, Proceedings of the EVOLVE 2012, Mexico City, Mexico, Advances in Intelligent and Soft Computing, 175:189-203, Springer 2012. |
|
|
| An Improved Memetic Algorithm for the Antibandwidth Problem. Eduardo Rodriguez-Tello and Luis Carlos Betancourt, Proceedings of the EA 2011, Angers France, Lecture Notes in Computer Science, 7401:120-132, Springer 2012. |
|
|
Request for information
If you are interested in finding out more information about the Covering Arrays generated during this research project, please fill out the form below.
