de.mpg.escidoc.pubman.appbase.FacesBean
Deutsch

Hilfe Wegweiser Impressum Kontakt Einloggen

# Datensatz

DATENSATZ AKTIONENEXPORT

Freigegeben

Bericht

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

##### MPG-Autoren

Dubhashi,  Devdatt P.
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

http://pubman.mpdl.mpg.de/cone/persons/resource/persons45021

Mehlhorn,  Kurt
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

http://pubman.mpdl.mpg.de/cone/persons/resource/persons45258

Ranjan,  Desh
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

http://pubman.mpdl.mpg.de/cone/persons/resource/persons45612

Thiel,  Christian
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

##### Externe Ressourcen
Es sind keine Externen Ressourcen verfügbar
##### Volltexte (frei zugänglich)

MPI-I-93-154.pdf
(beliebiger Volltext), 5MB

##### Ergänzendes Material (frei zugänglich)
Es sind keine frei zugänglichen Ergänzenden Materialien verfügbar
##### Zitation

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.

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.