article

A simple randomized parallel algorithm for list-ranking

Authors:

R. J. Anderson,

G. L. MillerAuthors Info & Claims

Information Processing Letters, Volume 33, Issue 5

Pages 269 - 273

https://doi.org/10.1016/0020-0190(90)90196-5

Published: 10 January 1990 Publication History

Abstract

No abstract available.

Cited By

View all

Ghaffari MGrunau CQu JAgrawal KShun J(2023)Nearly Work-Efficient Parallel DFS in Undirected GraphsProceedings of the 35th ACM Symposium on Parallelism in Algorithms and Architectures10.1145/3558481.3591094(273-283)Online publication date: 17-Jun-2023
https://dl.acm.org/doi/10.1145/3558481.3591094
Blelloch GFineman JGu YSun YScheideler CSpear M(2020)Optimal Parallel Algorithms in the Binary-Forking ModelProceedings of the 32nd ACM Symposium on Parallelism in Algorithms and Architectures10.1145/3350755.3400227(89-102)Online publication date: 6-Jul-2020
https://dl.acm.org/doi/10.1145/3350755.3400227
Entenza JHaeusler ELifschitz S(2020)Efficient Out-of-Core Contig GenerationAdvances in Bioinformatics and Computational Biology10.1007/978-3-030-65775-8_3(25-37)Online publication date: 23-Nov-2020
https://dl.acm.org/doi/10.1007/978-3-030-65775-8_3
Show More Cited By

Index Terms

A simple randomized parallel algorithm for list-ranking

Recommendations

Deterministic parallel list ranking
Abstract
In this paper we describe a simple parallel algorithm for list ranking. The algorithm is deterministic and runs inO(logn) time on an EREW PRAM withn/logn processors. The algorithm matches the performance of the Cole-Vishkin [CV3] algorithm but is ...
Constant-Time Randomized Parallel String Matching

Given a pattern string of length m for the string-matching problem, we design an algorithm that computes deterministic samples of a sufficiently long substring of the pattern in constant time. This problem used to be the bottleneck in the pattern ...
A Simple and Efficient Randomized Byzantine Agreement Algorithm

A new randomized Byzantine agreement algorithm is presented. This algorithm operates in a synchronous system of n processors, at most t of which can fail. The algorithm reaches agreement in 0(t/log n) expected rounds and O(n2tf/log n) expected message ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

Information Processing Letters Volume 33, Issue 5

January 1990

51 pages

ISSN:0020-0190

Editor:
S. G. Aki
Queen's Univ., Kingston, Canada

Issue’s Table of Contents

Publisher

Elsevier North-Holland, Inc.

United States

Publication History

Published: 10 January 1990

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

14
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 14 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Ghaffari MGrunau CQu JAgrawal KShun J(2023)Nearly Work-Efficient Parallel DFS in Undirected GraphsProceedings of the 35th ACM Symposium on Parallelism in Algorithms and Architectures10.1145/3558481.3591094(273-283)Online publication date: 17-Jun-2023
https://dl.acm.org/doi/10.1145/3558481.3591094
Blelloch GFineman JGu YSun YScheideler CSpear M(2020)Optimal Parallel Algorithms in the Binary-Forking ModelProceedings of the 32nd ACM Symposium on Parallelism in Algorithms and Architectures10.1145/3350755.3400227(89-102)Online publication date: 6-Jul-2020
https://dl.acm.org/doi/10.1145/3350755.3400227
Entenza JHaeusler ELifschitz S(2020)Efficient Out-of-Core Contig GenerationAdvances in Bioinformatics and Computational Biology10.1007/978-3-030-65775-8_3(25-37)Online publication date: 23-Nov-2020
https://dl.acm.org/doi/10.1007/978-3-030-65775-8_3
Ben-David NBlelloch GFineman JGibbons PGu YMcGuffey CShun JScheideler CGilbert S(2016)Parallel Algorithms for Asymmetric Read-Write CostsProceedings of the 28th ACM Symposium on Parallelism in Algorithms and Architectures10.1145/2935764.2935767(145-156)Online publication date: 11-Jul-2016
https://dl.acm.org/doi/10.1145/2935764.2935767
Banerjee DKumar AChaitanya MSharma SKothapalli K(2015)Work efficient parallel algorithms for large graph exploration on emerging heterogeneous architecturesJournal of Parallel and Distributed Computing10.1016/j.jpdc.2014.11.00676:C(81-93)Online publication date: 1-Feb-2015
https://dl.acm.org/doi/10.1016/j.jpdc.2014.11.006
Demetrescu CEscoffier BMoruz GRibichini A(2010)Adapting parallel algorithms to the W-Stream model, with applications to graph problemsTheoretical Computer Science10.5555/2912583.2912685411:44(3994-4004)Online publication date: 25-Oct-2010
https://dl.acm.org/doi/10.5555/2912583.2912685
Blelloch GMaggs B(2010)Parallel algorithmsAlgorithms and theory of computation handbook10.5555/1882723.1882748(25-25)Online publication date: 1-Jan-2010
https://dl.acm.org/doi/10.5555/1882723.1882748
Rehman MKothapalli KNarayanan PGschwind MNicolau ASalapura VMoreira J(2009)Fast and scalable list ranking on the GPUProceedings of the 23rd international conference on Supercomputing10.1145/1542275.1542311(235-243)Online publication date: 8-Jun-2009
https://dl.acm.org/doi/10.1145/1542275.1542311
Demetrescu CEscoffier BMoruz GRibichini A(2007)Adapting parallel algorithms to the W-stream model, with applications to graph problemsProceedings of the 32nd international conference on Mathematical Foundations of Computer Science10.5555/2392236.2392262(194-205)Online publication date: 26-Aug-2007
https://dl.acm.org/doi/10.5555/2392236.2392262
Arge LBender MDemaine EHolland-Minkley BMunro JReif J(2002)Cache-oblivious priority queue and graph algorithm applicationsProceedings of the thiry-fourth annual ACM symposium on Theory of computing10.1145/509907.509950(268-276)Online publication date: 19-May-2002
https://dl.acm.org/doi/10.1145/509907.509950
Show More Cited By

View Options

View options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Abstract

Cited By

Index Terms

Recommendations

Deterministic parallel list ranking

Constant-Time Randomized Parallel String Matching

A Simple and Efficient Randomized Byzantine Agreement Algorithm

Comments

Information

Published In

Publisher

Publication History

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

Get Access

Login options

Full Access

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations