Geodesic
On the complexity of sorting of Boolean algebra
Diskretnaya Matematika, Tome 3 (1991) no. 1, pp. 42-47

Voir la notice de l'article provenant de la source Math-Net.Ru

We consider a class of algorithms for finding the order on an $n$-element set that is isomorphic to a Boolean algebra by means of successive pairwise comparison of its elements. We assume that some comparisons can be made incorrectly and that, moreover, the general number of erroneous comparisons does not exceed a given value $k(n)$. We show that if $k=o(\log n)$, then the optimal algorithm has the same asymptotics of complexity as the optimal algorithm when $k=0$. 
@article{DM_1991_3_1_a2,
     author = {V. V. Morozenko},
     title = {On the complexity of sorting of {Boolean} algebra},
     journal = {Diskretnaya Matematika},
     pages = {42--47},
     publisher = {mathdoc},
     volume = {3},
     number = {1},
     year = {1991},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_1991_3_1_a2/}
}
TY  - JOUR
AU  - V. V. Morozenko
TI  - On the complexity of sorting of Boolean algebra
JO  - Diskretnaya Matematika
PY  - 1991
SP  - 42
EP  - 47
VL  - 3
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DM_1991_3_1_a2/
LA  - ru
ID  - DM_1991_3_1_a2
ER  - 
%0 Journal Article
%A V. V. Morozenko
%T On the complexity of sorting of Boolean algebra
%J Diskretnaya Matematika
%D 1991
%P 42-47
%V 3
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DM_1991_3_1_a2/
%G ru
%F DM_1991_3_1_a2
V. V. Morozenko. On the complexity of sorting of Boolean algebra. Diskretnaya Matematika, Tome 3 (1991) no. 1, pp. 42-47. http://geodesic.mathdoc.fr/item/DM_1991_3_1_a2/