Geodesic
Analysis of a new skip list variant
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

For a skip list variant, introduced by Cho and Sahni, we analyse what is the analogue of horizontal plus vertical search cost in the original skip list model. While the average in Pugh's original version behaves like $Q \log_Q n$, with $Q = \frac{1}{q}$ a parameter, it is here given by $(Q+1) \log_Q n$. 
@article{DMTCS_2006_special_252_a0,
     author = {Louchard, Guy and Prodinger, Helmut},
     title = {Analysis of a new skip list variant},
     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.3476},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3476/}
}
TY  - JOUR
AU  - Louchard, Guy
AU  - Prodinger, Helmut
TI  - Analysis of a new skip list variant
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.3476/
DO  - 10.46298/dmtcs.3476
LA  - en
ID  - DMTCS_2006_special_252_a0
ER  - 
%0 Journal Article
%A Louchard, Guy
%A Prodinger, Helmut
%T Analysis of a new skip list variant
%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.3476/
%R 10.46298/dmtcs.3476
%G en
%F DMTCS_2006_special_252_a0
Louchard, Guy; Prodinger, Helmut. Analysis of a new skip list variant. 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.3476. http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3476/

Cité par Sources :