Geodesic
On the lower bound for minimum comparison selection
Applications of Mathematics, Tome 23 (1978) no. 1, pp. 1-8
Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

DOI : 10.21136/AM.1978.103726
Classification : 68C25, 68E05, 68Q25, 68R99
Keywords: minimum comparison; selection algorithm; worst-case complexity; lower bound; adversary strategy; selection problem 
@article{10_21136_AM_1978_103726,
     author = {R\r{u}\v{z}i\v{c}ka, Peter and Wiedermann, Juraj},
     title = {On the lower bound for minimum comparison selection},
     journal = {Applications of Mathematics},
     pages = {1--8},
     year = {1978},
     volume = {23},
     number = {1},
     doi = {10.21136/AM.1978.103726},
     mrnumber = {0480156},
     zbl = {0418.68061},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.21136/AM.1978.103726/}
}
TY  - JOUR
AU  - Růžička, Peter
AU  - Wiedermann, Juraj
TI  - On the lower bound for minimum comparison selection
JO  - Applications of Mathematics
PY  - 1978
SP  - 1
EP  - 8
VL  - 23
IS  - 1
UR  - http://geodesic.mathdoc.fr/articles/10.21136/AM.1978.103726/
DO  - 10.21136/AM.1978.103726
LA  - en
ID  - 10_21136_AM_1978_103726
ER  - 
%0 Journal Article
%A Růžička, Peter
%A Wiedermann, Juraj
%T On the lower bound for minimum comparison selection
%J Applications of Mathematics
%D 1978
%P 1-8
%V 23
%N 1
%U http://geodesic.mathdoc.fr/articles/10.21136/AM.1978.103726/
%R 10.21136/AM.1978.103726
%G en
%F 10_21136_AM_1978_103726
Růžička, Peter; Wiedermann, Juraj. On the lower bound for minimum comparison selection. Applications of Mathematics, Tome 23 (1978) no. 1, pp. 1-8. doi: 10.21136/AM.1978.103726

[1] M. Blum R. W. Floyd V. Pratt R. Rivest R. Tarjan: Time bounds for selection. JCSS 7 (Aug. 1973), 448-461. | MR

[2] L. Hyafil: Bounds for selection. IRIA Rapport de Recherche n° 77. 1974. | MR

[3] D. E. Knuth: The art of computer programming. Volume 3. Sorting and Searching. Addison-Wesley publishing company. 1973. | MR

[4] V. Pratt F. F. Yao: On lower bounds for computing the i-th largest elements. Proceedings of the Fourteenth Symposium on Switching and Automata Theory. 1973. | MR

[5] A. Schönhage M. Paterson N. Pippenger: Finding the median. Theory of Computation Report. The University of Warwick. 1975. | MR

Cité par Sources :