Explicit constructions for perfect hash families |
| |
Authors: | Sosina Martirosyan Tran van Trung |
| |
Institution: | 1. University of Houston-Clear Lake, 2700 Bay Area Blvd., Houston, TX, 77058, U.S.A 2. Institut für Experimentelle Mathematik, Universit?t Duisburg-Essen, Ellernstrasse 29, 45326, Essen, Germany
|
| |
Abstract: | Let k, v, t be integers such that k ≥ v ≥ t ≥ 2. A perfect hash family (N; k, v, t) can be defined as an N × k array with entries from a set of v symbols such that every N × t subarray contains at least one row having distinct symbols. Perfect hash families have been studied by over 20 years and
they find a wide range of applications in computer sciences and in cryptography. In this paper we focus on explicit constructions
for perfect hash families using combinatorial methods. We present many recursive constructions which result in a large number
of improved parameters for perfect hash families. The paper also includes extensive tables for parameters with t = 3, 4, 5, 6 of newly constructed perfect hash families.
|
| |
Keywords: | Perfect hash family Combinatorial method Explicit construction |
本文献已被 SpringerLink 等数据库收录! |
|