|
This article is cited in 1 scientific paper (total 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$.
 Full text:
PDF file (592 kB)
English version:
Discrete Mathematics and Applications, 1992, 2:3, 313–318
Bibliographic databases:
 
UDC:
519.712, 519.718.3
Received: 19.07.1989
Citation:
V. V. Morozenko, “On the complexity of sorting of Boolean algebra”, Diskr. Mat., 3:1 (1991), 42–47; Discrete Math. Appl., 2:3 (1992), 313–318
Citation in format AMSBIB
\Bibitem{Mor91}
\by V.~V.~Morozenko
\paper On the complexity of sorting of Boolean algebra
\jour Diskr. Mat.
\yr 1991
\vol 3
\issue 1
\pages 42--47
\mathnet{http://mi.mathnet.ru/dm773}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=1112286}
\zmath{https://zbmath.org/?q=an:0825.68407}
\transl
\jour Discrete Math. Appl.
\yr 1992
\vol 2
\issue 3
\pages 313--318
Linking options:
http://mi.mathnet.ru/eng/dm773 http://mi.mathnet.ru/eng/dm/v3/i1/p42
Citing articles on Google Scholar:
Russian citations,
English citations
Related articles on Google Scholar:
Russian articles,
English articles
This publication is cited in the following articles:
-
Yu. B. Nikitin, “On the sorting complexity of Cartesian products of partially ordered sets”, Discrete Math. Appl., 11:4 (2001), 373–390
 
|
| Number of views: |
| This page: | 247 | | Full text: | 97 | | First page: | 1 |
|
Terms of Use