Upper Bounds on the Size of Covering Arrays

DOI10.1137/16M1067767zbMath1365.05039arXiv1603.07809OpenAlexW2963501551MaRDI QIDQ5270407

Kaushik Sarkar, Charles J. Colbourn

Publication date: 23 June 2017

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1603.07809

zbMATH Keywords

Lovász local lemmacovering arrayconditional expectation algorithm

Mathematics Subject Classification ID

Optimal statistical designs (62K05) Searching and sorting (68P10) Partitions of sets (05A18) Other designs, configurations (05B30) Extremal combinatorics (05D99)

Related Items (8)

On a combinatorial framework for fault characterization ⋮ Do judge a test by its cover. Combining combinatorial and property-based testing ⋮ Asymptotic and constructive methods for covering perfect hash families and covering arrays ⋮ The Lovász local lemma and variable strength covering arrays ⋮ Partial covering arrays: algorithms and asymptotics ⋮ Directed Lovász local lemma and Shearer's lemma ⋮ Arrays for combinatorial interaction testing: a review on constructive approaches ⋮ Upper bounds on the sizes of variable strength covering arrays using the Lovász local lemma

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Constructing strength three covering arrays with augmented annealing
• Tabu search for covering arrays using permutation vectors
• Merging covering arrays and compressing multiple sequence alignments
• Approximation algorithms for combinatorial problems
• On the ratio of optimal integral and fractional covers
• Covering arrays of strength three
• Two combinatorial covering theorems
• Improving two recursive constructions for covering arrays
• Sperner capacities
• Two applications (for search theory and truth functions) of Sperner type theorems
• Families of \(k\)-independent sets
• A survey of combinatorial testing
• A constructive proof of the general lovász local lemma
• Vector sets for exhaustive testing of logic circuits
• Group construction of covering arrays
• t-Covering Arrays: Upper Bounds and Poisson Approximations
• A constructive proof of the Lovász local lemma
• Two‐stage algorithms for covering array construction
• Covering Array Bounds Using Analytical Techniques
• Asymptotic Size of Covering Arrays: An Application of Entropy Compression
• New Constructive Aspects of the Lovász Local Lemma
• $t$-Covering Arrays Generated by a Tiling Probability Model

This page was built for publication: Upper Bounds on the Size of Covering Arrays