| Title:
|
On the lower bound for minimum comparison selection (English) |
| Author:
|
Růžička, Peter |
| Author:
|
Wiedermann, Juraj |
| Language:
|
English |
| Journal:
|
Aplikace matematiky |
| ISSN:
|
0373-6725 |
| Volume:
|
23 |
| Issue:
|
1 |
| Year:
|
1978 |
| Pages:
|
1-8 |
| Summary lang:
|
Slovak |
| . |
| Category:
|
math |
| . |
| Keyword:
|
minimum comparison |
| Keyword:
|
selection algorithm |
| Keyword:
|
worst-case complexity |
| Keyword:
|
lower bound |
| Keyword:
|
adversary strategy |
| Keyword:
|
selection problem |
| MSC:
|
68C25 |
| MSC:
|
68E05 |
| MSC:
|
68Q25 |
| MSC:
|
68R99 |
| idZBL:
|
Zbl 0418.68061 |
| idMR:
|
MR0480156 |
| DOI:
|
10.21136/AM.1978.103726 |
| . |
| Date available:
|
2008-05-20T18:08:37Z |
| Last updated:
|
2020-07-28 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/103726 |
| . |
| Reference:
|
[1] M. Blum R. W. Floyd V. Pratt R. Rivest R. Tarjan: Time bounds for selection.JCSS 7 (Aug. 1973), 448-461. MR 0329916 |
| Reference:
|
[2] L. Hyafil: Bounds for selection.IRIA Rapport de Recherche n° 77. 1974. MR 0464673 |
| Reference:
|
[3] D. E. Knuth: The art of computer programming. Volume 3. Sorting and Searching.Addison-Wesley publishing company. 1973. MR 0445948 |
| Reference:
|
[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 0468319 |
| Reference:
|
[5] A. Schönhage M. Paterson N. Pippenger: Finding the median.Theory of Computation Report. The University of Warwick. 1975. MR 0428794 |
| . |
