Upper bounds on the sizes of variable strength covering arrays using the Lovász local lemma

DOI10.1016/j.tcs.2019.10.022zbMath1487.05042arXiv1901.05386OpenAlexW2980425835WikidataQ124832901 ScholiaQ124832901MaRDI QIDQ2333832

Lucia Moura, Sebastian Raaphorst, Brett Stevens

Publication date: 13 November 2019

Published in: Theoretical Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

greedy algorithmderandomizationLovász local lemmacovering arraysvariable strength

Mathematics Subject Classification ID

Combinatorics on words (68R15) Other designs, configurations (05B30) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Related Items

Algorithmic methods for covering arrays of higher index

Uses Software

• OpenOpt

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Binary consecutive covering arrays
• A construction for strength-3 covering arrays from linear feedback shift register sequences
• Partial covering arrays: algorithms and asymptotics
• Constructing new covering arrays from LFSR sequences over finite fields
• Asymptotic lower bounds for Ramsey functions
• Probabilistic methods for algorithmic discrete mathematics
• Asymptotic and constructive methods for covering perfect hash families and covering arrays
• The Lovász local lemma and variable strength covering arrays
• Counting designs
• Consecutive covering arrays and a new randomness test
• A constructive proof of the general lovász local lemma
• Variable strength covering arrays
• t-Covering Arrays: Upper Bounds and Poisson Approximations
• Two‐stage algorithms for covering array construction
• Covering Array Bounds Using Analytical Techniques
• Upper Bounds on the Size of Covering Arrays
• Asymptotic Size of Covering Arrays: An Application of Entropy Compression