Optimal parallel randomized renaming

Martin Farach, S. Muthukrishnan

    Research output: Contribution to journalArticlepeer-review


    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
    Issue number1
    StatePublished - Jan 14 1997


    • PRAM algorithm
    • Renaming problem

    ASJC Scopus subject areas

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


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

    Cite this