Back to Search Start Over

Deterministic parallel list ranking

Authors :
Richard J. Anderson
Gary L. Miller
Source :
VLSI Algorithms and Architectures ISBN: 0387968180, AWOC
Publication Year :
2006
Publisher :
Springer-Verlag, 2006.

Abstract

In this paper we describe a simple parallel algorithm for list ranking. The algorithm is deterministic and runs in O(log n) time on EREW P-RAM with n/log n processor. The algorithm matches the performance of the Cole-Vishkin [CV86a] algorithm but is simple and has reasonable constant factors.

Subjects

Subjects :
List update problem
Computer science
Simple (abstract algebra)
Parallel prefix
List ranking
Parallel algorithm
Self-organizing list
Constant (mathematics)
Binary logarithm
Algorithm

Details

ISBN :
978-0-387-96818-6
0-387-96818-0
ISBNs :
9780387968186 and 0387968180
Database :
OpenAIRE
Journal :
VLSI Algorithms and Architectures ISBN: 0387968180, AWOC
Accession number :
edsair.doi...........ce038a354898254b88f9d24c73940b29

Tools

Authors Abstract Subjects Details