# Item

ITEM ACTIONSEXPORT

Released

Report

#### Searching, sorting and randomised algorithms for central elements and ideal counting in posets

##### MPS-Authors

##### Locator

There are no locators available

##### Fulltext (public)

MPI-I-93-154.pdf

(Any fulltext), 5MB

##### Supplementary Material (public)

There is no public supplementary material available

##### Citation

Dubhashi, D. P., Mehlhorn, K., Ranjan, D., & Thiel, C.(1993). *Searching,
sorting and randomised algorithms for central elements and ideal counting in posets* (MPI-I-93-154). Saarbrücken:
Max-Planck-Institut für Informatik.

Cite as: http://hdl.handle.net/11858/00-001M-0000-0014-B76C-B

##### Abstract

By the Central Element Theorem of Linial and Saks, it follows that for
the problem of (generalised) searching in posets, the
information--theoretic lower bound of $\log N$ comparisons (where $N$ is the
number of order--ideals in the poset) is tight asymptotically. We
observe that this implies that the problem of (generalised) sorting
in posets has complexity $\Theta(n \cdot \log N)$ (where $n$ is the
number of elements in the poset). We present schemes for
(efficiently) transforming a randomised generation procedure for
central elements (which often exists for some classes of posets) into
randomised procedures for approximately counting ideals in the poset
and for testing if an arbitrary element is central.