Optimal parallel randomized renaming

Martin Farach, S. Muthukrishnan

    Research output: Contribution to journalArticlepeer-review

    Abstract

    We consider the Renaming Problem, a basic processing step in string algorithms, for which we give a simultaneously work and time optimal Las Vegas type PRAM algorithm. The Renaming Problem is closely related to the Multiset Sorting Problem.

    Original languageEnglish (US)
    Pages (from-to)7-10
    Number of pages4
    JournalInformation Processing Letters
    Volume61
    Issue number1
    DOIs
    StatePublished - Jan 14 1997

    Keywords

    • PRAM algorithm
    • Renaming problem

    ASJC Scopus subject areas

    • Theoretical Computer Science
    • Signal Processing
    • Information Systems
    • Computer Science Applications

    Fingerprint Dive into the research topics of 'Optimal parallel randomized renaming'. Together they form a unique fingerprint.

    Cite this