Bipartite random graphs and Cuckoo hashing

zbMATH Open1191.68207MaRDI QIDQ3575013FDOQ3575013

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

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

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)

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)