Partial covering arrays: algorithms and asymptotics

DOI10.1007/s00224-017-9782-9zbMath1391.68085arXiv1605.02131OpenAlexW2963856226MaRDI QIDQ726106

Ugo Vaccaro, Kaushik Sarkar, Annalisa De Bonis, Charles J. Colbourn

Publication date: 3 August 2018

Published in: Lecture Notes in Computer Science, Theory of Computing Systems (Search for Journal in Brave)

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

zbMATH Keywords

combinatorial designorthogonal arrayscovering arrayspartial covering arrayssoftware interaction testing

Mathematics Subject Classification ID

Combinatorics in computer science (68R05) Orthogonal arrays, Latin squares, Room squares (05B15) Randomized algorithms (68W20)

Related Items (6)

Attribute-efficient learning of Boolean functions from Post closed classes ⋮ Partial covering arrays for data hiding and quantization ⋮ A greedy-metaheuristic 3-stage approach to construct covering arrays ⋮ Algebraic techniques for covering arrays and related structures ⋮ Asymptotic and constructive methods for covering perfect hash families and covering arrays ⋮ 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
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On sets of Boolean \(n\)-vectors with all \(k\)-projections surjective
• How robust is the n-cube?
• Subcube fault-tolerance in hypercubes
• Approximation algorithms for combinatorial problems
• On the ratio of optimal integral and fractional covers
• Covering arrays of strength three
• Adaptive versus nonadaptive attribute-efficient learning
• Exact learning of juntas from membership queries
• Two combinatorial covering theorems
• Problems and algorithms for covering arrays
• Sperner capacities
• Two applications (for search theory and truth functions) of Sperner type theorems
• Families of \(k\)-independent sets
• Extremal Combinatorics
• A constructive proof of the general lovász local lemma
• Group construction of covering arrays
• t-Covering Arrays: Upper Bounds and Poisson Approximations
• Upper Bounds on the Size of Covering Arrays
• Optimal Two-Stage Algorithms for Group Testing Problems
• Asymptotic Size of Covering Arrays: An Application of Entropy Compression

This page was built for publication: Partial covering arrays: algorithms and asymptotics