Optimal parallel randomized renaming

Martin Farach, S. Muthukrishnan

Research output: Contribution to journalArticlepeer-review

2 Scopus citations


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

All Science Journal Classification (ASJC) codes

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


  • PRAM algorithm
  • Renaming problem


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

Cite this