Maximum matchings in random bipartite graphs and the space utilization of Cuckoo Hash tables
Maximum matchings in random bipartite graphs and the space utilization of Cuckoo Hash tables
复制标题
随机二部图中的最大匹配与布谷鸟哈希表的空间利用率
DOI：
--
复制
发表时间：
2009
期刊：
影响因子：
--
通讯作者：
Páll Melsted
中科院分区：
文献类型：
--
作者：
A. Frieze;Páll Melsted
我们在随机图中研究以下问题。讨论的问题是G中最大的匹配的大小（G）。当D至少是三
We study the the following question in Random Graphs. We are given two disjoint sets L,R with |L| = n and |R| = m. We construct a random graph G by allowing each x∈L to choose d random neighbours in R. The question discussed is as to the size μ(G) of the largest matching in G. When considered in the context of Cuckoo Hashing, one key question is as to when is μ(G) = n whp? We answer this question exactly when d is at least three. © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2012