This article is cited in 1 paper

On the complexity of sorting of Boolean algebra

V. V. Morozenko


Abstract: 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$.

UDC: 519.712, 519.718.3

Received: 19.07.1989

 English version: Discrete Mathematics and Applications, 1992, 2:3, 313–318

Bibliographic databases:

• 
•