Bipartite random graphs and Cuckoo hashing

MaRDI QIDQ3575013zbMATH OpenFDO

Authors Reinhard Kutzelnigg

Publication date 5 July 2010

Full work available at URL https://www.dmtcs.org/dmtcs-ojs/index.php/proceedings/article/view/dmAG0133/0.html

zbMATH Keywords

generating functionshashingrandom bipartite graphsdouble saddle point method

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Data structures (68P05)

Recommendations

• A precise analysis of cuckoo hashing
• Maximum matchings in random bipartite graphs and the space utilization of cuckoo hash tables
• A further analysis of cuckoo hashing with a stash and random graphs of excess \(r\)
• Cuckoo hashing: Further analysis
• Almost random graphs with simple hash functions

Cited in

(10)

• A faster algorithm for cuckoo insertion and bipartite matching in large graphs
• Load thresholds for cuckoo hashing with double hashing
• Cuckoo hashing in cryptography: optimal parameters, robustness and applications
• Maximum matchings in random bipartite graphs and the space utilization of cuckoo hash tables
• Efficient no-dictionary verifiable searchable symmetric encryption
• A precise analysis of cuckoo hashing
• An improved version of cuckoo hashing: average case analysis of construction cost and search operations
• Convergence of multivariate belief propagation, with applications to cuckoo hashing and load balancing
• Almost random graphs with simple hash functions
• Tight thresholds for Cuckoo hashing via XORSAT (extended abstract)

This page was built for publication: Bipartite random graphs and Cuckoo hashing

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