Optimal parallel randomized renaming

Martin Farach; S. Muthukrishnan

doi:10.1016/s0020-0190(96)00182-2

Optimal parallel randomized renaming

Martin Farach, S. Muthukrishnan

School of Arts and Sciences, Computer Science

Research output: Contribution to journal › Article › peer-review

2 Scopus citations

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 language	English (US)
Pages (from-to)	7-10
Number of pages	4
Journal	Information Processing Letters
Volume	61
Issue number	1
DOIs	https://doi.org/10.1016/s0020-0190(96)00182-2
State	Published - Jan 14 1997

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Signal Processing
Information Systems
Computer Science Applications

Keywords

PRAM algorithm
Renaming problem

Access to Document

10.1016/s0020-0190(96)00182-2

Cite this

@article{6e50f8e55c404f13a042f21932039cfe,

title = "Optimal parallel randomized renaming",

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.",

keywords = "PRAM algorithm, Renaming problem",

author = "Martin Farach and S. Muthukrishnan",

note = "Funding Information: * Corresponding author. Email: farach@cs.rutgers.edu. by an NSF Career Advancement Award. {\textquoteright} Email: muthu@dcs.warwick.ac.uk. Supported by DIMACS (Center for Discrete Mathematics and Theoretical Computer Science), a National Science Foundation Science and Technology Center under NSF contract STC-8809648.",

year = "1997",

month = jan,

day = "14",

doi = "10.1016/s0020-0190(96)00182-2",

language = "English (US)",

volume = "61",

pages = "7--10",

journal = "Information Processing Letters",

issn = "0020-0190",

publisher = "Elsevier",

number = "1",

}

TY - JOUR

T1 - Optimal parallel randomized renaming

AU - Farach, Martin

AU - Muthukrishnan, S.

N1 - Funding Information: * Corresponding author. Email: farach@cs.rutgers.edu. by an NSF Career Advancement Award. ’ Email: muthu@dcs.warwick.ac.uk. Supported by DIMACS (Center for Discrete Mathematics and Theoretical Computer Science), a National Science Foundation Science and Technology Center under NSF contract STC-8809648.

PY - 1997/1/14

Y1 - 1997/1/14

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

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

KW - PRAM algorithm

KW - Renaming problem

UR - http://www.scopus.com/inward/record.url?scp=0030736468&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0030736468&partnerID=8YFLogxK

U2 - 10.1016/s0020-0190(96)00182-2

DO - 10.1016/s0020-0190(96)00182-2

M3 - Article

AN - SCOPUS:0030736468

SN - 0020-0190

VL - 61

SP - 7

EP - 10

JO - Information Processing Letters

JF - Information Processing Letters

IS - 1

ER -

Optimal parallel randomized renaming

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this