id: 05526553
dt: a
an: 05526553
au: Colbourn, Charles J.
ti: Constructing perfect hash families using a greedy algorithm.
so: Li, Yongqing (ed.) et al., Coding and cryptology. Proceedings of the first
    international workshop, Wuyi Mountain, Fujian, China, June 11‒15,
    2007. Hackensack, NJ: World Scientific (ISBN 978-981-283-223-8/hbk).
    Series on Coding Theory and Cryptology 4, 109-124 (2008).
py: 2008
pu: Hackensack, NJ: World Scientific
la: EN
cc: 
ut: 
ci: 
li: doi:10.1142/9789812832245_0008
ab: Summary: A perfect hash family $\text{PHF}(N;k,v,t)$ is an $N\times k$
    array on $v$ symbols with $v\ge t$, in which in every $N\times t$
    subarray, at least one row is comprised of distinct symbols. Perfect
    hash families have a wide range of applications in cryptography,
    particularly to secure frameproof codes, in database management, and
    are indirectly used in software interaction testing. A simple
    one-row-at-a-time greedy algorithm for constructing small perfect hash
    families is described. The algorithm is deterministic, and its
    worst-case runtime is polynomial in $k$ and $v$ but exponential in $t$;
    consequently, when $t$ is fixed, the algorithm runs in polynomial time
    in the worst case. It provides a deterministic guarantee that the
    number $N$ of rows produced is $O(\log k)$. In addition to these strong
    asymptotic guarantees, the method is shown to be practical for the
    computation of perfect hash families for “small" values of $k$ and
    $t$.
rv: