Name
Abstract | ||
|---|---|---|
In this paper we deal with the problem of finding the smallest and the largest elements of a totally ordered set of size n using pairwise comparisons if one of the comparisons might be erroneous and prove a conjecture of Aigner stating that the minimum number of comparisons needed is 87n32+c for some constant c. We also address some related problems. |
Year | DOI | Venue |
|---|---|---|
2010 | 10.1016/j.dam.2010.01.010 | Discrete Applied Mathematics |
Keywords | Field | DocType |
constant c,search,sorting,related problem,minimum number,minimum element,size n,largest element,pairwise comparison,erroneous information,total order | Ordered set,Pairwise comparison,Discrete mathematics,Combinatorics,Total order,Sorting,Conjecture,Mathematics | Journal |
Volume | Issue | ISSN |
158 | 9 | Discrete Applied Mathematics |
Citations | PageRank | References |
1 | 0.38 | 4 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Dániel Gerbner | 1 | 46 | 21.61 |
| Dömötör Pálvölgyi | 2 | 202 | 29.14 |
| Balázs Patkós | 3 | 85 | 21.60 |
| Gábor Wiener | 4 | 64 | 10.65 |