{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,11]],"date-time":"2026-03-11T19:56:01Z","timestamp":1773258961006,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":50,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540578994","type":"print"},{"value":"9783540483854","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1994]]},"DOI":"10.1007\/3-540-57899-4_49","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T13:40:14Z","timestamp":1330263614000},"page":"153-165","source":"Crossref","is-referenced-by-count":7,"title":["Graphs, hypergraphs and hashing"],"prefix":"10.1007","author":[{"given":"George","family":"Havas","sequence":"first","affiliation":[]},{"given":"Bohdan S.","family":"Majewski","sequence":"additional","affiliation":[]},{"given":"Nicholas C.","family":"Wormald","sequence":"additional","affiliation":[]},{"given":"Zbigniew J.","family":"Czech","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,5,26]]},"reference":[{"key":"14_CR1","unstructured":"A.V. Aho, J.E. Hopcroft, and J.D. Ullman. The Design and Analysis of Computer Algorithms. Addison-Wesley, 1974."},{"key":"14_CR2","doi-asserted-by":"crossref","first-page":"967","DOI":"10.1002\/spe.4380191005","volume":"19","author":"M. D. Brain","year":"1989","unstructured":"M.D. Brain and A.L. Tharp. Near-perfect hashing of large word sets. Software \u2014 Practice and Experience 19 (1989) 967\u2013978.","journal-title":"Software \u2014 Practice and Experience"},{"key":"14_CR3","doi-asserted-by":"crossref","first-page":"281","DOI":"10.1016\/0306-4379(90)90001-6","volume":"15","author":"M. D. Brain","year":"1990","unstructured":"M.D. Brain and A.L. Tharp. Perfect hashing using sparse matrix packing. Information Systems, 15 (1990) 281\u2013290.","journal-title":"Information Systems"},{"key":"14_CR4","doi-asserted-by":"crossref","unstructured":"J.L. Carter and M.N. Wegman. Universal classes of hash functions. In 9th Annual ACM Symposium on Theory of Computing \u2014 STOC'77, 106\u2013112, 1977.","DOI":"10.1145\/800105.803400"},{"key":"14_CR5","doi-asserted-by":"crossref","unstructured":"J.L. Carter and M.N. Wegman. New classes and applications of hash functions. In 20th Annual Symposium on Foundations of Computer Science \u2014 FOCS'79, 175\u2013182, 1979a.","DOI":"10.1109\/SFCS.1979.26"},{"key":"14_CR6","doi-asserted-by":"crossref","first-page":"143","DOI":"10.1016\/0022-0000(79)90044-8","volume":"18","author":"J. L. Carter","year":"1979","unstructured":"J.L. Carter and M.N. Wegman. Universal classes of hash functions. Journal of Computer and System Sciences, 18 (1979b) 143\u2013154.","journal-title":"Journal of Computer and System Sciences"},{"key":"14_CR7","doi-asserted-by":"crossref","first-page":"38","DOI":"10.1109\/MS.1985.232067","volume":"2","author":"N. Cercone","year":"1985","unstructured":"N. Cercone, J. Boates, and M. Krause. An interactive system for finding perfect hash functions. IEEE Software, 2 (1985) 38\u201353.","journal-title":"IEEE Software"},{"key":"14_CR8","doi-asserted-by":"crossref","first-page":"35","DOI":"10.1002\/spe.4380210104","volume":"21","author":"C-C. Chang","year":"1991","unstructured":"C-C. Chang and T-C. Wu. Letter oriented perfect hashing scheme based upon sparse table compression. Software \u2014 Practice and Experience, 21 (1991) 35\u201349.","journal-title":"Software \u2014 Practice and Experience"},{"key":"14_CR9","doi-asserted-by":"crossref","first-page":"384","DOI":"10.1145\/358027.358051","volume":"27","author":"C. C. Chang","year":"1984","unstructured":"C.C. Chang. The study of an ordered minimal perfect hashing scheme. Communications of the ACM, 27 (1984) 384\u2013387.","journal-title":"Communications of the ACM"},{"key":"14_CR10","doi-asserted-by":"crossref","first-page":"79","DOI":"10.1016\/0020-0190(88)90096-8","volume":"27","author":"C. C. Chang","year":"1988","unstructured":"C.C. Chang and C.H. Chang. An ordered minimal perfect hashing scheme with single parameter. Information Processing Letters, 27 (1988) 79\u201383.","journal-title":"Information Processing Letters"},{"key":"14_CR11","doi-asserted-by":"crossref","first-page":"469","DOI":"10.1093\/comjnl\/34.5.469","volume":"34","author":"C. C. Chang","year":"1991","unstructured":"C.C. Chang, C.Y. Chen, and J.K. Jan. On the design of a machine independent perfect hashing. The Computer Journal, 34 (1991) 469\u2013474.","journal-title":"The Computer Journal"},{"key":"14_CR12","doi-asserted-by":"crossref","first-page":"277","DOI":"10.1093\/comjnl\/29.3.277","volume":"29","author":"C. C. Chang","year":"1986","unstructured":"C.C. Chang and R.C.T. Lee. A letter-oriented minimal perfect hashing scheme. The Computer Journal, 29 (1986) 277\u2013281.","journal-title":"The Computer Journal"},{"key":"14_CR13","doi-asserted-by":"crossref","first-page":"17","DOI":"10.1145\/358808.358813","volume":"23","author":"R. J. Cichelli","year":"1980","unstructured":"R.J. Cichelli. Minimal perfect hash functions made simple. Communications of the ACM, 23 (1980) 17\u201319.","journal-title":"Communications of the ACM"},{"key":"14_CR14","doi-asserted-by":"crossref","first-page":"18","DOI":"10.1145\/947955.947957","volume":"17","author":"C. R. Cook","year":"1982","unstructured":"C.R. Cook and R.R. Oldehoeft. A letter oriented minimal perfect hashing function. SIGPLAN Notices, 17 (1982) 18\u201327.","journal-title":"SIGPLAN Notices"},{"key":"14_CR15","doi-asserted-by":"crossref","first-page":"54","DOI":"10.1093\/comjnl\/28.1.54","volume":"28","author":"G. V. Cormack","year":"1985","unstructured":"G.V. Cormack, R.N.S. Horspool, and M. Kaiserwerth. Practical perfect hashing. The Computer Journal, 28 (1985) 54\u201355.","journal-title":"The Computer Journal"},{"key":"14_CR16","doi-asserted-by":"crossref","first-page":"257","DOI":"10.1016\/0020-0190(92)90220-P","volume":"43","author":"Z. J. Czech","year":"1992","unstructured":"Z.J. Czech, G. Havas, and B.S. Majewski. An optimal algorithm for generating minimal perfect hash functions. Information Processing Letters, 43 (1992) 257\u2013264.","journal-title":"Information Processing Letters"},{"key":"14_CR17","first-page":"3","volume":"4","author":"Z. J. Czech","year":"1992","unstructured":"Z.J. Czech and B.S. Majewski. Generating a minimal perfect hashing function in O(m 2) time. Archiwum Informatyki, 4 (1992) 3\u201320.","journal-title":"Archiwum Informatyki"},{"key":"14_CR18","doi-asserted-by":"crossref","unstructured":"M. Dietzfelbinger, J. Gil, Y. Matias, and N. Pippenger. Polynomial hash functions are reliable. In 19th International Colloquium on Automata, Languages and Programming \u2014 ICALP'92, 235\u2013246, Vienna, Austria, 1992. LNCS 623.","DOI":"10.1007\/3-540-55719-9_77"},{"key":"14_CR19","first-page":"6","volume-title":"LNCS 443","author":"M. Dietzfelbinger","year":"1990","unstructured":"M. Dietzfelbinger and F. Meyer auf der Heide. A new universal class of hash functions, and dynamic hashing in real time. In 17th International Colloquium on Automata, Languages and Programming \u2014 ICALP'90, 6\u201319, Warwick University, England, 1990. LNCS 443."},{"key":"14_CR20","doi-asserted-by":"crossref","first-page":"305","DOI":"10.1109\/TSE.1983.236866","volume":"9","author":"M. W. Du","year":"1983","unstructured":"M.W. Du, T.M. Hsieh, K.F. Jea, and D.W Shieh. The study of a new perfect hash scheme. IEEE Transactions on Software Engineering, 9 (1983) 305\u2013313.","journal-title":"IEEE Transactions on Software Engineering"},{"key":"14_CR21","first-page":"399","volume":"27","author":"R. Duke","year":"1985","unstructured":"R. Duke. Types of cycles in hypergraphs. Ann. Discrete Math., 27 (1985) 399\u2013418.","journal-title":"Ann. Discrete Math."},{"key":"14_CR22","first-page":"17","volume":"5","author":"P. Erd\u0151s","year":"1960","unstructured":"P. Erd\u0151s and A. R\u00e9nyi. On the evolution of random graphs. Publ. Math. Inst. Hung. Acad. Sci., 5 (1960) 17\u201361. Reprinted in J.H. Spencer, editor, The Art of Counting: Selected Writings, Mathematicians of Our Time, 574\u2013617. Cambridge, Mass.: MIT Press, 1973.","journal-title":"Publ. Math. Inst. Hung. Acad. Sci."},{"key":"14_CR23","doi-asserted-by":"crossref","first-page":"281","DOI":"10.1145\/125187.125200","volume":"9","author":"E. Fox","year":"1991","unstructured":"E. Fox, Q.F. Chen, A. Daoud, and L. Heath. Order preserving minimal perfect hash functions and information retrieval. ACM Transactions on Information Systems, 9 (1991) 281\u2013308.","journal-title":"ACM Transactions on Information Systems"},{"key":"14_CR24","doi-asserted-by":"crossref","unstructured":"E. Fox, Q.F. Chen, and L. Heath. LEND and faster algorithms for constructing minimal perfect hash functions. In Proc. 15th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval \u2014 SIGIR'92, Copenhagen, Denmark, 266\u2013273, 1992.","DOI":"10.1145\/133160.133209"},{"key":"14_CR25","doi-asserted-by":"crossref","first-page":"105","DOI":"10.1145\/129617.129623","volume":"35","author":"E. A. Fox","year":"1992","unstructured":"E.A. Fox, L.S. Heath, Q. Chen, and A.M. Daoud. Practical minimal perfect hash functions for large databases. Communications of the ACM, 35 (1992) 105\u2013121.","journal-title":"Communications of the ACM"},{"key":"14_CR26","doi-asserted-by":"crossref","first-page":"538","DOI":"10.1145\/828.1884","volume":"31","author":"M. L. Fredman","year":"1984","unstructured":"M.L. Fredman, J. Koml\u00f3s, and E. Szemer\u00e9di. Storing a sparse table with O(1) worst case access time. Journal of the ACM, 31 (1984) 538\u2013544.","journal-title":"Journal of the ACM"},{"key":"14_CR27","volume-title":"Handbook of Algorithms and Data Structures","author":"G. H. Gonnet","year":"1991","unstructured":"G.H. Gonnet and R. Baeza-Yates. Handbook of Algorithms and Data Structures. Addison-Wesley, Reading, Mass., 1991."},{"key":"14_CR28","doi-asserted-by":"crossref","first-page":"209","DOI":"10.1007\/BF01932700","volume":"29","author":"M. Gori","year":"1989","unstructured":"M. Gori and G. Soda. An algebraic approach to Cichelli's perfect hashing. BIT, 29 (1989) 209\u2013214.","journal-title":"BIT"},{"key":"14_CR29","doi-asserted-by":"crossref","first-page":"191","DOI":"10.1145\/953055.5899","volume":"18","author":"G. Haggard","year":"1986","unstructured":"G. Haggard and K. Karplus. Finding minimal perfect hash functions. ACM SIGCSE Bulletin, 18 (1986) 191\u2013193.","journal-title":"ACM SIGCSE Bulletin"},{"key":"14_CR30","volume-title":"Technical Report 234","author":"G. Havas","year":"1992","unstructured":"G. Havas and B.S. Majewski. Optimal algorithms for minimal perfect hashing. Technical Report 234, The University of Queensland, Key Centre for Software Technology, Queensland, 1992."},{"key":"14_CR31","doi-asserted-by":"crossref","first-page":"43","DOI":"10.1016\/0020-0190(86)90041-4","volume":"22","author":"C. T. M. M. Jackobs","year":"1986","unstructured":"C.T.M. Jackobs and P. van Emde Boas. Two results on tables. Information Processing Letters, 22 (1986) 43\u201348.","journal-title":"Information Processing Letters"},{"key":"14_CR32","doi-asserted-by":"crossref","first-page":"829","DOI":"10.1145\/358800.358806","volume":"24","author":"G. Jaeschke","year":"1981","unstructured":"G. Jaeschke. Reciprocal hashing: A method for generating minimal perfect hashing functions. Communications of the ACM, 24 (1981) 829\u2013833.","journal-title":"Communications of the ACM"},{"key":"14_CR33","doi-asserted-by":"crossref","unstructured":"A. Karlin and E. Upfal. Parallel hashing \u2014 an efficient implementation of shared memory. In 18th Annual ACM Symposium on Theory of Computing \u2014 STOC'86, 160\u2013168, 1986.","DOI":"10.1145\/12130.12146"},{"key":"14_CR34","doi-asserted-by":"crossref","first-page":"45","DOI":"10.1109\/2.7056","volume":"21","author":"T. G. Lewis","year":"1988","unstructured":"T.G. Lewis and C.R. Cook. Hashing for dynamic and static internal tables. Computer, 21 (1988) 45\u201356.","journal-title":"Computer"},{"key":"14_CR35","volume-title":"Technical Report 16","author":"B. S. Majewski","year":"1992","unstructured":"B.S. Majewski, N.C. Wormald, Z.J. Czech, and G. Havas. A family of generators of minimal perfect hash functions. Technical Report 16, DIMACS, Rutgers University, New Jersey, USA, 1992."},{"key":"14_CR36","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-69672-5","volume-title":"Data Structures and Algorithms 1: Sorting and Searching, volume 1","author":"K. Mehlhorn","year":"1984","unstructured":"K. Mehlhorn. Data Structures and Algorithms 1: Sorting and Searching, volume 1. Springer-Verlag, Berlin Heidelberg, New York, Tokyo, 1984."},{"key":"14_CR37","doi-asserted-by":"crossref","unstructured":"F. Meyer auf der Heide. Dynamic hashing strategies. In 15th Symposium on Mathematical Foundations of Computer Science \u2014 MFCS'90, 76\u201387, Banska Bystrica, Czechoslovakia, 1990.","DOI":"10.1007\/BFb0029597"},{"key":"14_CR38","doi-asserted-by":"crossref","first-page":"677","DOI":"10.1145\/78973.78978","volume":"33","author":"P. K. Pearson","year":"1990","unstructured":"P.K. Pearson. Fast hashing of variable-length text strings. Communications of the ACM, 33 (1990) 677\u2013680.","journal-title":"Communications of the ACM"},{"key":"14_CR39","doi-asserted-by":"crossref","first-page":"523","DOI":"10.1145\/3532.3538","volume":"28","author":"T. J. Sager","year":"1985","unstructured":"T.J. Sager. A polynomial time generator for minimal perfect hash functions. Communications of the ACM, 28 (1985) 523\u2013532.","journal-title":"Communications of the ACM"},{"key":"14_CR40","doi-asserted-by":"crossref","unstructured":"J.P. Schmidt and A. Siegel. On aspects of universality and performance for closed hashing. In 21st Annual ACM Symposium on Theory of Computing \u2014 STOC'89, 355\u2013366, Seattle, Washington, 1989.","DOI":"10.1145\/73007.73041"},{"key":"14_CR41","doi-asserted-by":"crossref","unstructured":"J.P. Schmidt and A. Siegel. The analysis of closed hashing under limited randomness. In 22st Annual ACM Symposium on Theory of Computing \u2014 STOC'90, 224\u2013234, Baltimore, MD, 1990.","DOI":"10.1145\/100216.100245"},{"key":"14_CR42","doi-asserted-by":"crossref","first-page":"775","DOI":"10.1137\/0219054","volume":"19","author":"J. P. Schmidt","year":"1990","unstructured":"J.P. Schmidt and A. Siegel. The spatial complexity of oblivious k-probe hash functions. SIAM Journal on Computing, 19 (1990) 775\u2013786.","journal-title":"SIAM Journal on Computing"},{"key":"14_CR43","doi-asserted-by":"crossref","unstructured":"A. Siegel. On universal classes of fast high performance hash functions, their timespace trade-off, and their applications. In 30th Annual Symposium on Foundations of Computer Science \u2014 FOCS'89, 20\u201325, 1989.","DOI":"10.1109\/SFCS.1989.63450"},{"key":"14_CR44","doi-asserted-by":"crossref","unstructured":"C. Slot and P. van Emde Boas. On tape versus core: An application of space efficient hash functions to the invariance of space. In 16th Annual ACM Symposium on Theory of Computing \u2014 STOC'84, 391\u2013400, Washington, DC, 1984.","DOI":"10.1145\/800057.808705"},{"key":"14_CR45","unstructured":"J. Spencer and N.C. Wormald. On the k-core of random graphs. Manuscript, 1993."},{"key":"14_CR46","doi-asserted-by":"crossref","first-page":"841","DOI":"10.1145\/359863.359887","volume":"20","author":"R. Sprugnoli","year":"1977","unstructured":"R. Sprugnoli. Perfect hashing functions: A single probe retrieving method for static sets. Communications of the ACM, 20 (1977) 841\u2013850.","journal-title":"Communications of the ACM"},{"key":"14_CR47","doi-asserted-by":"crossref","first-page":"606","DOI":"10.1145\/359168.359175","volume":"22","author":"R. E. Tarjan","year":"1979","unstructured":"R.E. Tarjan and A.C-C Yao. Storing a sparse table. Communications of the ACM, 22 (1979) 606\u2013611.","journal-title":"Communications of the ACM"},{"key":"14_CR48","doi-asserted-by":"crossref","unstructured":"V.G. Winters. Minimal perfect hashing for large sets of data. In International Conference on Computing and Information \u2014 ICCI'90, 275\u2013284, Niagara Falls, Canada, 1990.","DOI":"10.1007\/3-540-53504-7_85"},{"key":"14_CR49","doi-asserted-by":"crossref","first-page":"235","DOI":"10.1007\/BF02017345","volume":"30","author":"V. G. Winters","year":"1990","unstructured":"V.G. Winters. Minimal perfect hashing in polynomial time. BIT, 30 (1990) 235\u2013244.","journal-title":"BIT"},{"key":"14_CR50","doi-asserted-by":"crossref","first-page":"148","DOI":"10.1007\/BF01934995","volume":"25","author":"W. P. Yang","year":"1985","unstructured":"W.P. Yang and M.W. Du. A backtracking method for constructing perfect hash functions from a set of mapping functions. BIT, 25 (1985) 148\u2013164.","journal-title":"BIT"}],"container-title":["Lecture Notes in Computer Science","Graph-Theoretic Concepts in Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-57899-4_49.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,21]],"date-time":"2025-03-21T22:16:32Z","timestamp":1742595392000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-57899-4_49"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1994]]},"ISBN":["9783540578994","9783540483854"],"references-count":50,"URL":"https:\/\/doi.org\/10.1007\/3-540-57899-4_49","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[1994]]}}}