Geodesic
Bipartite Random Graphs and Cuckoo Hashing
Discrete mathematics & theoretical computer science, DMTCS Proceedings vol. AG, Fourth Colloquium on Mathematics and Computer Science Algorithms, Trees, Combinatorics and Probabilities, DMTCS Proceedings vol. AG, Fourth Colloquium on Mathematics and Computer Science Algorithms, Trees, Combinatorics and Probabilities (2006).

Voir la notice de l'article provenant de la source Episciences

The aim of this paper is to extend the analysis of Cuckoo Hashing of Devroye and Morin in 2003. In particular we make several asymptotic results much more precise. We show, that the probability that the construction of a hash table succeeds, is asymptotically $1-c(\varepsilon)/m+O(1/m^2)$ for some explicit $c(\varepsilon)$, where $m$ denotes the size of each of the two tables, $n=m(1- \varepsilon)$ is the number of keys and $\varepsilon \in (0,1)$. The analysis rests on a generating function approach to the so called Cuckoo Graph, a random bipartite graph. We apply a double saddle point method to obtain asymptotic results covering tree sizes, the number of cycles and the probability that no complex component occurs. 
@article{DMTCS_2006_special_252_a10,
     author = {Kutzelnigg, Reinhard},
     title = {Bipartite {Random} {Graphs} and {Cuckoo} {Hashing}},
     journal = {Discrete mathematics & theoretical computer science},
     publisher = {mathdoc},
     volume = {DMTCS Proceedings vol. AG, Fourth Colloquium on Mathematics and Computer Science Algorithms, Trees, Combinatorics and Probabilities},
     year = {2006},
     doi = {10.46298/dmtcs.3486},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3486/}
}
TY  - JOUR
AU  - Kutzelnigg, Reinhard
TI  - Bipartite Random Graphs and Cuckoo Hashing
JO  - Discrete mathematics & theoretical computer science
PY  - 2006
VL  - DMTCS Proceedings vol. AG, Fourth Colloquium on Mathematics and Computer Science Algorithms, Trees, Combinatorics and Probabilities
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3486/
DO  - 10.46298/dmtcs.3486
LA  - en
ID  - DMTCS_2006_special_252_a10
ER  - 
%0 Journal Article
%A Kutzelnigg, Reinhard
%T Bipartite Random Graphs and Cuckoo Hashing
%J Discrete mathematics & theoretical computer science
%D 2006
%V DMTCS Proceedings vol. AG, Fourth Colloquium on Mathematics and Computer Science Algorithms, Trees, Combinatorics and Probabilities
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3486/
%R 10.46298/dmtcs.3486
%G en
%F DMTCS_2006_special_252_a10
Kutzelnigg, Reinhard. Bipartite Random Graphs and Cuckoo Hashing. Discrete mathematics & theoretical computer science, DMTCS Proceedings vol. AG, Fourth Colloquium on Mathematics and Computer Science Algorithms, Trees, Combinatorics and Probabilities, DMTCS Proceedings vol. AG, Fourth Colloquium on Mathematics and Computer Science Algorithms, Trees, Combinatorics and Probabilities (2006). doi : 10.46298/dmtcs.3486. http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3486/

Cité par Sources :