Two-Way Chaining with Reassignment

DOI10.1137/S0097539704443240MaRDI QIDQ5470693zbMATH OpenOpenAlexFDO

Authors Ketan Dalal, Ebrahim Malalla, Erin McLeish, Luc Devroye

Publication date 1 June 2006

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/s0097539704443240

zbMATH Keywords

hashingprobabilistic analysis of algorithmsrandom graphstwo-way chainingworst-case search time

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Searching and sorting (68P10) Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40)

Recommendations

• Two-way chaining for non-uniform distributions
• scientific article; zbMATH DE number 1875412
• Cuckoo hashing
• On the insertion time of cuckoo hashing
• On probabilistic analysis of a coalesced hashing algorithm

Cited in

(5)

• On the k-orientability of random graphs
• Two-way chaining for non-uniform distributions
• Dynamic dictionaries for multisets and counting filters with constant time operations
• An improved version of cuckoo hashing: average case analysis of construction cost and search operations
• Dynamic dictionaries for multisets and counting filters with constant time operations

This page was built for publication: Two-Way Chaining with Reassignment

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5470693)