Geodesic
On the sorting complexity of Cartesian products of partially ordered sets
Diskretnaya Matematika, Tome 13 (2001) no. 3, pp. 57-74
Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

We study the complexity $L(M_n)$ of algorithms for sorting the partially ordered set $M_n$, which is isomorphic to the Cartesian product $$ K_1\times\ldots\times K_n, $$ where all $K_i$ are taken from some finite family, have a unique maximum element, and are prime with respect to the Cartesian product. For the set $\{M_n\}$, as $n\to\infty$, we obtain the estimates \begin{align*} L(M_n)\gtrsim|M_n|\log_{2}|M_n|, \\ L(M_n)\lesssim(|K_1|+\ldots+|K_n|)|M_n|. \end{align*} Besides, we prove that for a partially ordered set with one maximum element the Cartesian decomposition into prime factors is unique up to a permutation of the factors. 
@article{DM_2001_13_3_a3,
     author = {Yu. B. Nikitin},
     title = {On the sorting complexity of {Cartesian} products of partially ordered sets},
     journal = {Diskretnaya Matematika},
     pages = {57--74},
     year = {2001},
     volume = {13},
     number = {3},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_2001_13_3_a3/}
}
TY  - JOUR
AU  - Yu. B. Nikitin
TI  - On the sorting complexity of Cartesian products of partially ordered sets
JO  - Diskretnaya Matematika
PY  - 2001
SP  - 57
EP  - 74
VL  - 13
IS  - 3
UR  - http://geodesic.mathdoc.fr/item/DM_2001_13_3_a3/
LA  - ru
ID  - DM_2001_13_3_a3
ER  - 
%0 Journal Article
%A Yu. B. Nikitin
%T On the sorting complexity of Cartesian products of partially ordered sets
%J Diskretnaya Matematika
%D 2001
%P 57-74
%V 13
%N 3
%U http://geodesic.mathdoc.fr/item/DM_2001_13_3_a3/
%G ru
%F DM_2001_13_3_a3
Yu. B. Nikitin. On the sorting complexity of Cartesian products of partially ordered sets. Diskretnaya Matematika, Tome 13 (2001) no. 3, pp. 57-74. http://geodesic.mathdoc.fr/item/DM_2001_13_3_a3/

[1] Akho A. V., Khopkroft Dzh., Ulman Dzh., Postroenie i analiz vychislitelnykh algoritmov, Mir, Moskva, 1979 | MR | Zbl

[2] Knut D., Iskusstvo programmirovaniya dlya EVM. Sortirovka i poisk, t. 3., Mir, Moskva, 1978 | MR | Zbl

[3] Morozenko V. V., “O slozhnosti sortirovki bulevoi algebry”, Diskretnaya matematika, 3:1 (1991), 42–47 | Zbl

[4] Borovkov A. A., Teoriya veroyatnostei, Nauka, Moskva, 1986 | MR | Zbl

[5] Faigle U., Turan G., “Sorting and recognition problems for ordered sets”, SIAM J. Comput., 17:1 (1988), 100–113 | DOI | MR | Zbl