Maximum matchings in random bipartite graphs and the space utilization of Cuckoo Hash tables

DOI10.1002/rsa.20427zbMath1252.05175arXiv0910.5535OpenAlexW2080908560WikidataQ57401438 ScholiaQ57401438MaRDI QIDQ3168498

Páll Melsted, Alan M. Frieze

Publication date: 31 October 2012

Published in: Random Structures & Algorithms (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/0910.5535

zbMATH Keywords

random bipartite graphcuckoo hashing

Mathematics Subject Classification ID

Searching and sorting (68P10) Extremal problems in graph theory (05C35) Random graphs (graph-theoretic aspects) (05C80) Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Data structures (68P05)

Related Items (13)

Online Stochastic Matching: Online Actions Based on Offline Statistics ⋮ Load Thresholds for Cuckoo Hashing with Overlapping Blocks ⋮ Matchings on infinite graphs ⋮ Load Thresholds for Cuckoo Hashing with Overlapping Blocks ⋮ Orientability Thresholds for Random Hypergraphs ⋮ The Multiple-Orientability Thresholds for Random Hypergraphs ⋮ Thresholds for extreme orientability ⋮ Unnamed Item ⋮ Unnamed Item ⋮ A new approach to the orientation of random hypergraphs ⋮ A faster algorithm for cuckoo insertion and bipartite matching in large graphs ⋮ Fast scalable construction of ([compressed static | minimal perfect hash) functions] ⋮ Towards optimal degree distributions for left-perfect matchings in random bipartite graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Finite size scaling for the core of large random hypergraphs
• Cuckoo hashing: Further analysis
• Matchings in random regular bipartite digraphs
• A probabilistic proof of an asymptotic formula for the number of labelled regular graphs
• Existence of a perfect matching in a random (\(1+e^{-1}\))-out bipartite graph
• The 3-XORSAT threshold.
• Space efficient hash tables with worst case constant access time
• Sharp load thresholds for cuckoo hashing
• Tight Thresholds for Cuckoo Hashing via XORSAT
• Some Open Questions Related to Cuckoo Hashing
• Balanced Allocations
• Efficient erasure correcting codes
• Cuckoo hashing
• Cores in random hypergraphs and Boolean formulas

This page was built for publication: Maximum matchings in random bipartite graphs and the space utilization of Cuckoo Hash tables