Perfect Hash Families: The Generalization to Higher Indices
Date
2020
Journal Title
Journal ISSN
Volume Title
Publisher
Springer
Abstract
Perfect hash families are often represented as combinatorial arrays encoding partitions of k items into v classes, so that every t or fewer of the items are completely separated by at least a speci fied number of the chosen partitions. This specified number is the index of the hash family. The case when each t-set must be separated at least once has been extensively researched; they arise in diverse applications, both directly and as fundamental ingredients in a column replacement strategy for a variety of combinatorial arrays. In this paper, construction techniques and algorithmic methods for constructing perfect hash families are surveyed, in order to explore extensions to the situation when each t-set must be separated by more than one partition.
Description
item.page.type
Books, book chapters
item.page.format
Keywords
Hash Families, Construction Techniques, Algorithmic Methods
Citation
Dougherty, R.E., Colbourn, C.J. (2020). Perfect Hash Families: The Generalization to Higher Indices. In: Raigorodskii, A.M., Rassias, M.T. (eds) Discrete Mathematics and Applications. Springer Optimization and Its Applications, vol 165. Springer, Cham. https://doi.org/10.1007/978-3-030-55857-4_7