Asymptotic and constructive methods for covering perfect hash families and covering arrays

DOI10.1007/s10623-017-0369-xzbMath1383.05045OpenAlexW2619826047MaRDI QIDQ1741930

Kaushik Sarkar, Erin Lanus, Charles J. Colbourn

Publication date: 10 April 2018

Published in: Designs, Codes and Cryptography (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10623-017-0369-x

zbMATH Keywords

asymptotic boundcovering arrayconditional expectation algorithmcovering perfect hash family

Mathematics Subject Classification ID

Orthogonal arrays, Latin squares, Room squares (05B15) Combinatorial structures in finite projective spaces (51E20) Combinatorial aspects of packing and covering (05B40) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40) Group actions on combinatorial structures (05E18)

Related Items (14)

On a combinatorial framework for fault characterization ⋮ Algorithms for Constructing Anonymizing Arrays ⋮ Covering schemes of strength \(t\) ⋮ Detecting arrays for effects of single factors ⋮ A greedy-metaheuristic 3-stage approach to construct covering arrays ⋮ An extension of a construction of covering arrays ⋮ The Lovász local lemma and variable strength covering arrays ⋮ Subspace restrictions and affine composition for covering perfect hash families ⋮ Improved covering arrays using covering perfect hash families with groups of restricted entries ⋮ Arrays for combinatorial interaction testing: a review on constructive approaches ⋮ In-parameter-order strategies for covering perfect hash families ⋮ Upper bounds on the sizes of variable strength covering arrays using the Lovász local lemma ⋮ Algorithmic methods for covering arrays of higher index ⋮ Heuristically enhanced IPO algorithms for covering array generation

Uses Software

• AETG

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A construction for strength-3 covering arrays from linear feedback shift register sequences
• Partial covering arrays: algorithms and asymptotics
• Roux-type constructions for covering arrays of strengths three and four
• Constructing new covering arrays from LFSR sequences over finite fields
• A polynomial algorithm for constructing families of k-independent sets
• Constructing strength three covering arrays with augmented annealing
• Tabu search for covering arrays using permutation vectors
• Covering arrays from cyclotomy
• 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
• Improved strength four covering arrays with three symbols
• Randomized post-optimization of covering arrays
• Two combinatorial covering theorems
• On \(t\)-covering arrays
• Improving two recursive constructions for covering arrays
• Sperner capacities
• Strength two covering arrays: existence tables and projection
• A survey of combinatorial testing
• On the state of strength-three covering arrays
• 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
• Covering Array Bounds Using Analytical Techniques
• Upper Bounds on the Size of Covering Arrays
• Asymptotic Size of Covering Arrays: An Application of Entropy Compression
• $t$-Covering Arrays Generated by a Tiling Probability Model
• Covering arrays of higher strength from permutation vectors

This page was built for publication: Asymptotic and constructive methods for covering perfect hash families and covering arrays