Optimal parallel randomized renaming

Martin Farach, S. Muthukrishnan

    Research output: Contribution to journalArticle

    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
    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

    Farach, M., & Muthukrishnan, S. (1997). Optimal parallel randomized renaming. Information Processing Letters, 61(1), 7-10.