Perfect Hash Families: The Generalization to Higher Indices
Loading...
Authors
Dougherty, Ryan E.
Colbourn, Charles J.
Issue Date
2020
Type
Books, book chapters
Language
Keywords
Hash Families , Construction Techniques , Algorithmic Methods
Alternative Title
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
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
Publisher
Springer