Covering array on the Cartesian product of hypergraphs
Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Structural characterization of families of graphs (05C75) Graph operations (line graphs, products, etc.) (05C76) Approximation algorithms (68W25)
A covering array is a mathematical object used in designing the experiment for combinatorial testing. In industrial applications, the columns of the covering array denote factors of the system and every row points a test to be performed. As the cost of the testing is proportional to the size of the covering array, the cost-optimization and hence minimizing the size of a covering array is pertinent in an application environment. It is known that finding an optimal covering array on a hypergraph is NP-hard. The authors here mainly focus on the covering array on the Cartesian product of Cayley hypergraphs and successfully endeavored to build an optimal covering array on a large hypergraph by taking clues from the product of smaller hypergraphs. They nicely obtain a polynomial-time approximation algorithm for constructing a covering array on a 3-uniform hypergraph of bounded degree, with \(k>1\) prime factors with respect to the Cartesian product of hypergraphs. They also indicate directions for further research.
- hClique: An exact algorithm for maximum clique problem in uniform hypergraphs
- A construction for strength-3 covering arrays from linear feedback shift register sequences
- A hyperedge coloring and application in combinatorial testing
- Binary covering arrays on tournaments
- Cayley hypergraphs and Cayley hypermaps
- Cayley, Marty and Schreier hypergraphs
- Compressing inconsistent data
- Cost-efficient mixed-level covering designs for testing experiments
- Covering arrays on graphs
- Explicit construction of exponential sized families of k-independent sets
- Factorization of products of hypergraphs: Structure and algorithms
- Hypergraph theory. An introduction
- Introduction to combinatorial testing
- Mixed covering arrays on 3-uniform hypergraphs
- Mixed covering arrays on graphs
- New constructions for IPP codes
- Orthogonal Arrays of Index Unity
- Orthogonal arrays. Theory and applications
- Problems and algorithms for covering arrays
- Software and hardware testing using combinatorial covering suites
- The Cartesian product of hypergraphs
- Variable strength covering arrays
- Vector sets for exhaustive testing of logic circuits
- Über das schwache Kartesische Produkt von Graphen
This page was built for publication: Covering array on the Cartesian product of hypergraphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6581902)
