Tabu search for covering arrays using permutation vectors

Robert A. Walker, Charles Colbourn

Research output: Contribution to journalArticlepeer-review

46 Scopus citations


A covering arrayCA (N ; t, k, v) is an N × k array, in which in every N × t subarray, each of the vt possible t-tuples over v symbols occurs at least once. The parameter t is the strength of the array. Covering arrays have a wide range of applications for experimental screening designs, particularly for software interaction testing. A compact representation of certain covering arrays employs "permutation vectors" to encode vt × 1 subarrays of the covering array so that a covering perfect hash family whose entries correspond to permutation vectors yields a covering array. We introduce a method for effective search for covering arrays of this type using tabu search. Using this technique, improved covering arrays of strength 3, 4 and 5 have been found, as well as the first arrays of strength 6 and 7 found by computational search.

Original languageEnglish (US)
Pages (from-to)69-80
Number of pages12
JournalJournal of Statistical Planning and Inference
Issue number1
StatePublished - Jan 2009


  • Covering array
  • Heuristic search
  • Orthogonal array
  • Permutation vector
  • Tabu search

ASJC Scopus subject areas

  • Statistics and Probability
  • Statistics, Probability and Uncertainty
  • Applied Mathematics


Dive into the research topics of 'Tabu search for covering arrays using permutation vectors'. Together they form a unique fingerprint.

Cite this