Perfect Hash Families: The Generalization to Higher Indices

Ryan E. Dougherty () and Charles J. Colbourn ()
Additional contact information
Ryan E. Dougherty: United States Military Academy
Charles J. Colbourn: Arizona State University

A chapter in Discrete Mathematics and Applications, 2020, pp 177-197 from Springer

Abstract: 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 specified number of 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.

Date: 2020
References: Add references at CitEc
Citations: View citations in EconPapers (1)

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:spochp:978-3-030-55857-4_7

Ordering information: This item can be ordered from
http://www.springer.com/9783030558574

DOI: 10.1007/978-3-030-55857-4_7

Access Statistics for this chapter

More chapters in Springer Optimization and Its Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().