Premium
Variable strength covering arrays
Author(s) -
Raaphorst Sebastian,
Moura Lucia,
Stevens Brett
Publication year - 2018
Publication title -
journal of combinatorial designs
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.618
H-Index - 34
eISSN - 1520-6610
pISSN - 1063-8539
DOI - 10.1002/jcd.21602
Subject(s) - hypergraph , mathematics , variable (mathematics) , homomorphism , combinatorics , order (exchange) , discrete mathematics , mathematical analysis , finance , economics
We define and study variable strength covering arrays (also called covering arrays on hypergraphs), which are generalizations of covering arrays and covering arrays on graphs. Variable strength covering arrays have the potential for use in software testing, allowing the engineer to omit the parameter combinations known to not interact in order to reduce the number of tests required. The present paper shows that variable strength covering arrays are relevant combinatorial objects that have deep connections with hypergraph homomorphisms and generalize other important combinatorial designs. We give optimal constructions for special types of hypergraphs, constructions based on columns with uniform occurrence of symbols, and constructions for mixed alphabets.