Geodesic
On the complexity of sorting of Boolean algebra
Diskretnaya Matematika, Tome 3 (1991) no. 1, pp. 42-47
Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

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},
     year = {1991},
     volume = {3},
     number = {1},
     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
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
%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/