Computer Science – Data Structures and Algorithms
Scientific paper
2009-10-29
Computer Science
Data Structures and Algorithms
Scientific paper
We study the the following question in Random Graphs. We are given two disjoint sets $L,R$ with $|L|=n=\alpha m$ and $|R|=m$. We construct a random graph $G$ by allowing each $x\in L$ to choose $d$ random neighbours in $R$. The question discussed is as to the size $\mu(G)$ of the largest matching in $G$. When considered in the context of Cuckoo Hashing, one key question is as to when is $\mu(G)=n$ whp? We answer this question exactly when $d$ is at least four. We also establish a precise threshold for when Phase 1 of the Karp-Sipser Greedy matching algorithm suffices to compute a maximum matching whp.
Frieze Alan
Melsted Pall
No associations
LandOfFree
Maximum Matchings in Random Bipartite Graphs and the Space Utilization of Cuckoo Hashtables does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Maximum Matchings in Random Bipartite Graphs and the Space Utilization of Cuckoo Hashtables, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Maximum Matchings in Random Bipartite Graphs and the Space Utilization of Cuckoo Hashtables will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-404229