de.mpg.escidoc.pubman.appbase.FacesBean
English
 
Help Guide Disclaimer Contact us Login
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT

Released

Report

Optimal parallel string algorithms: sorting, merching and computing the minimum

MPS-Authors
http://pubman.mpdl.mpg.de/cone/persons/resource/persons44564

Hagerup,  Torben
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

Locator
There are no locators available
Fulltext (public)

MPI-I-93-152.pdf
(Any fulltext), 14MB

Supplementary Material (public)
There is no public supplementary material available
Citation

Hagerup, T.(1993). Optimal parallel string algorithms: sorting, merching and computing the minimum (MPI-I-93-152). Saarbrücken: Max-Planck-Institut für Informatik.


Cite as: http://hdl.handle.net/11858/00-001M-0000-0014-B76A-F
Abstract
We study fundamental comparison problems on strings of characters, equipped with the usual lexicographical ordering. For each problem studied, we give a parallel algorithm that is optimal with respect to at least one criterion for which no optimal algorithm was previously known. Specifically, our main results are: % \begin{itemize} \item Two sorted sequences of strings, containing altogether $n$~characters, can be merged in $O(\log n)$ time using $O(n)$ operations on an EREW PRAM. This is optimal as regards both the running time and the number of operations. \item A sequence of strings, containing altogether $n$~characters represented by integers of size polynomial in~$n$, can be sorted in $O({{\log n}/{\log\log n}})$ time using $O(n\log\log n)$ operations on a CRCW PRAM. The running time is optimal for any polynomial number of processors. \item The minimum string in a sequence of strings containing altogether $n$ characters can be found using (expected) $O(n)$ operations in constant expected time on a randomized CRCW PRAM, in $O(\log\log n)$ time on a deterministic CRCW PRAM with a program depending on~$n$, in $O((\log\log n)^3)$ time on a deterministic CRCW PRAM with a program not depending on~$n$, in $O(\log n)$ expected time on a randomized EREW PRAM, and in $O(\log n\log\log n)$ time on a deterministic EREW PRAM. The number of operations is optimal, and the running time is optimal for the randomized algorithms and, if the number of processors is limited to~$n$, for the nonuniform deterministic CRCW PRAM algorithm as wel